[백준 C++] 2042번: 구간 합 구하기 (indexed tree)

1.문제

어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.

2. Solved.ac 난이도

3. 활용 알고리즘:  인덱스 트리

4. 틀린 이유: TLE

구간 내 값을 하나하나 더하면 시간초과를 피할 수 없음. 추가로 값의 변경이 수시로 일어나기 때문에 이를 더욱 효율적으로 관리해줄 인덱스 트리가 사용되어야함
값의 변경이 일어나지 않는다면 prefix sum을 이용해서도 풀이할 수 있음!

---

 

인덱스 트리는 구현보다 활용 하는 방법이 매번 헷갈리는 것 같다.

아래 sum 함수를 잘 확인해보도록하쟈!

시작구간의 인덱스가 홀수면 본인을 더한 뒤, +1해서 부모로 올라가고, 

끝구간의 인덱스가 짝수면 본인을 더한 뒤, -1해서 부모로 올라간다.

시작구간의 인덱스가 끙구간의 인덱스보다 크면 루프를 끝낸다.

 

최종 정답 코드

 

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
int e = 0,n;
long long int indexTree[1024 * 1024 * 2];
void swapp(int b,long long int c) {
	b += e-1;
	long long int gap = c - indexTree[b];
	for (int i = b; i >=1; i =i/2) {
		indexTree[i] +=gap;
	}
}
void sum(int b, int c) {
	b += e-1;
	c += e-1;
	long long int sum=0;
	while (b <= c) {
		if (b % 2 == 1)
			sum += indexTree[b];
		if (c % 2 == 0)
			sum += indexTree[c];
		b = (b + 1) / 2;
		c = (c - 1) / 2;
	}
	cout << sum<<endl;
}
int main() {
	int m,k;
	long long int a, b, c;
	scanf("%d %d %d", &n, &m, &k);
	int t = 0;

	while (t<n) {
		e++;
		t = 1<<e ;

	}
	e = 1 << e;
	for (int i = e; i < n+e; i++) {
		cin >> indexTree[i];
	}

	for (int i = e*2-1; i >1; i-=2) {
		indexTree[i / 2] = indexTree[i] + indexTree[i - 1];
	}
	for (int i = 0; i < m+k; i++) {
		cin >> a >> b >> c;
		if (a == 1) {
			swapp(b, c);
		}
		else if (a == 2) {
			sum(b, c);
		}
	}
	return 0;
}