백준 2042 구간 합 구하기 C++ 풀이 - 인덱스 트리

값이 빈번하게 수정될 때, 구간의 합을 효율적으로 구하라는 문제이다.

인덱스 트리나 세그먼트 트리 혹은 펜윅 트리를 강요하는 문제가 아닐까 싶다.

 

Bottom-up 방식으로 구성하는 인덱스 트리가 가장 쉬워서 인덱스 트리로 구현했다.

세그먼트 트리도 가능한데 물론, 구현하기가 쉽지 않아서.. (재귀) ㅠㅠ

 

인덱스 트리는 1차원 배열에다가 배정하며, (부모 인덱스 * 2 , 부모 인덱스 * 2 + 1) 이 자식의 인덱스이다.

물론 완전 이진 트리로 만든다.

 

고민할 점은, tree 배열을 선언할 때 할당할 메모리를 잘 생각해야 한다는 점이다.

데이터 수가 N 이면 2^n 으로 배정하여 부모-자식 사이의 관계가 유지되도록 만들어줘야 한다.

 

여기서 루트 노드의 인덱스는 1이고, 배열의 크기는 2^n 으로 보면 1024 * 1024 (2의 20승) 이므로

그것의 2배만큼 할당하면 트리 메모리는 충분하다.

 

base idx 는 리프 노드가 시작되는 idx를 말한다.

 

makeTree 는 리프 노드 바로 직전 인덱스부터 자식+자식으로 구성한다.(합 트리)

 

get 은 트리에서 범위 안에 속할 경우 부모로 올라오고,

부모가 달라서 올라올 수 없는 자식의 경우 ans 에 더해주고 더 이상 고려하지 않는다.

 

#include <cstdio>

#define _CRT_SECURE_NO_WARNINGS
using namespace std;

int N, M, K;
int a, b;
long long c;
long long tree[1024 * 1024 * 2 + 1];

int base_idx=1;
const int root = 1;

void print() {
	for (int i = 1; i < base_idx + N; i++) {
		printf("%d ", tree[i]);
	}
}
void update(int change_idx, long long change_delta) {
	while (change_idx >= root) {
		tree[change_idx] += change_delta;
		change_idx /= 2;
	}
}

void get(int start_idx, int end_idx) {
	long long ans = 0;
	while (start_idx < end_idx  ) {
		if (start_idx % 2 == 1) {
			ans += tree[start_idx];
			start_idx++;
		}
		if (end_idx % 2 == 0) {
			ans += tree[end_idx];
			end_idx--;
		}

		start_idx /= 2;
		end_idx /= 2;
		
	}
	if (start_idx == end_idx) {
		ans += tree[start_idx];
	}
	printf("%lld\n", ans);
}

void solve() {

	if (a == 1) {
		update(b + base_idx-1, c-tree[b+base_idx-1]);
	}
	else {
		get(b + base_idx -1 , c + base_idx - 1);
	}
}

void makeTree() {
	for (int i = base_idx - 1; i > 0; i--) {
		tree[i] = tree[2 * i] + tree[2 * i + 1];
	}
}


int main() {
	scanf("%d %d %d", &N, &M, &K);

	while (base_idx < N) base_idx *= 2;

	for (int i = 0; i < N; i++) {
		scanf("%lld", &tree[base_idx + i]);
	}
	makeTree();
	for (int i = 0; i < M + K; i++) {
		scanf("%d %d %lld", &a, &b, &c);
		solve();
	}
	return 0;
}