문제

숫자들의 부분합을 구하는 문제다.
예를 들어 1~10까지 배열에 있으면 2~4까지 합은 9다.

매번 구간을 순회한다면 n^2에 시간복잡도가 나올것이다.

그래서 이 시간 복잡도를 줄이기위해 이진 트리를 이용한다.
노드마다 범위를 정하고 자식들이 부모의 범위를 반씩 저장한다.

예를 들어 1번부터 5번까지 1~5를 저장한다면 다음과 같다.

말단 노드에는 해당 배열 값이 들어가고 부모노드는 자식노드들의 합이다.
그래서 해당 범위에 합을 구하고 싶으면 logn 시간복잡도가 나온다.

세그먼트 트리는 두가지 작업을 수행한다.
트리에 값을 넣는 삽입와 범위 합을 구하는 조회 행위.

update(삽입)

// update
// node 에서부터 start~end 사이값 idx 변경
void update(int node, int start, int end, int idx, LL val) {
	// 범위 체크
	if (idx < start || end < idx) return;
	// 리프 노드
	if (start == end) {
		tree[node] = val;
		return;
	}
	// 자식 업데이트
	update(2 * node, start, (start + end) / 2, idx, val);
	update(2 * node + 1,(start + end) / 2 + 1,end, idx, val);
	// 부모 변경
	tree[node] = tree[2 * node] + tree[2 * node + 1];
}

범위안에서 리프노드는 변경해주고
올라오면서 자식들을 업데이트해주고 본인의 노드값을 변경해주면 된다.

get_seg(조회)

// get_seg
// node에서부터 start~end 사이값에 l~r이 있는지 확인
LL get_seg(int node, int start, int end, int l, int r) {
	// 찾을게 없으면 리턴
	if (end < l || r < start) return 0;
	// 해당 범위면 반환
	if (l <= start && end <= r) return tree[node];
	// 양쪽 더한값 반환
	return get_seg(2 * node, start, (start + end) / 2, l, r) + get_seg(2 * node+1, (start + end) / 2 + 1, end, l, r);
}

조회는 찾고 싶은 범위를 정하면 left,right
노드의 범위를 줄여나가며 start,end
해당범위안이면 노드값을 반환하고 아니면 양쪽을 재귀적으로 조회한다.

relabeling

세그먼트 트리는 해당 인덱스 범위안에 합이 얼마인지 구하는데 사용할수있다.
근데 인덱스에 해당하는 값이 너무 크면 해당값을 상대적인 값으로 변경한다.

예를 들어 -10000, 0, 10000, 20000 이면 인덱스를 3만까지 저장하지 않고
1,2,3,4 처럼 상대적인 크기만 비교할수있도록 바꿀수있다.

이러한 relabeling은 구간합이 아닌 구간안에 상대적인 갯수를 구할때 사용된다.

처음 구현해봐서 어려웠는데
그림을 그려보고 삽입, 조회를 해보니 이해하기 좋았다.

code

/*
백준 2042
세그먼트 트리 구현
*/

#include <iostream>
#include <algorithm>
using namespace std;

#define N_MAX int(1e6)
typedef long long LL; // 8btye => 2^64 bit
int n, m, k;
// seg tree
LL tree[1<<21], arr[N_MAX + 1]; // 2&20 > 10^6

// get_seg
// node에서부터 start~end 사이값에 l~r이 있는지 확인
LL get_seg(int node, int start, int end, int l, int r) {
	// 찾을게 없으면 리턴
	if (end < l || r < start) return 0;
	// 해당 범위면 반환
	if (l <= start && end <= r) return tree[node];
	// 양쪽 더한값 반환
	return get_seg(2 * node, start, (start + end) / 2, l, r) + get_seg(2 * node+1, (start + end) / 2 + 1, end, l, r);
}
// update
// node 에서부터 start~end 사이값 idx 변경
void update(int node, int start, int end, int idx, LL val) {
	// 범위 체크
	if (idx < start || end < idx) return;
	// 리프 노드
	if (start == end) {
		tree[node] = val;
		return;
	}
	// 자식 업데이트
	update(2 * node, start, (start + end) / 2, idx, val);
	update(2 * node + 1,(start + end) / 2 + 1,end, idx, val);
	// 부모 변경
	tree[node] = tree[2 * node] + tree[2 * node + 1];
}
// start ~ end 범위안 idx 값을 변경
// 리프 노드는 arr로 초기화

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	
	// debug
	/*cout << "[arr] ";
	for (int i = 1; i <= n; i++) {
		printf("(%d,%d) ", i, arr[i]);
	}
	cout << endl;*/
	
	// init
	for (int i = 1; i <= n; i++) {
		// update
		update(1, 1, n, i,arr[i]);
	}

	// m+k
	for (int i = 0; i < m + k; i++) {
		LL cmd, a, b;
		cin >> cmd >> a >> b;
		// b를 c로 변경
		if (cmd == 1) {
			arr[a] = b;
			update(1, 1, n, a, b);
		}
		else {
			cout << get_seg(1, 1, n, a, b) << "\n";
		}
	}

}