c언어 2042번 구간 합 구하기 (백준)

#include <stdio.h>
typedef long long int ll;
ll a[1000000];
ll tree[4000000];

ll init(int s, int e, int node) { //트리 초기화
	if(s==e) return tree[node] = a[s];
	int mid = (s+e)/2;
	return tree[node] = init(s, mid, node*2) + init(mid+1, e, node*2+1);
} 

ll sum(int s, int e, int node, int l, int r) { //구간합 구하기
	if(s > r || e < l) return 0;
	if(l<=s && e <= r) return tree[node];
	int mid = (s+e)/2;
	return sum(s, mid, node*2, l, r) + sum(mid+1, e, node*2+1, l, r);
}

void update(int s, int e, int node, int index, ll dif) { //요소 바꾸기
	if(index < s || index > e) return;
	tree[node] += dif;
	if(s==e) return;
	int mid = (s+e)/2;
	update(s, mid, node*2, index, dif);
	update(mid+1, e, node*2+1, index, dif);
} 

int main(void) {
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);
	for(int i=0; i<n; i++) scanf("%lld", &a[i]);
	init(0, n-1, 1); //트리 초기화
	int cnt = m+k;
	while(cnt--) {
		ll b, c, d;
		scanf("%lld %lld %lld", &b, &c, &d);
		if(b==1) { //요소 초기화
			update(0, n-1, 1, c-1, d-a[c-1]); //관련된 트리의 값을 다 바꾼다
			a[c-1] = d; //요소가 바뀌었으니 a도 바꾸어 준다.
		}
		else {
			printf("%lld\n", sum(0, n-1, 1, c-1, d-1)); //구간합을 출력한다.
		}
	}
}

풀이 : segment tree (세그먼트 트리)

 

구간합을 구해야 하는 문제이나, 도중에 요소의 값을 바꿀 수 있기 때문에

단순히 누적합으로 구하는 것이 아닌 (누적합의 경우, 요소를 바꿀 때 마다 누적합들을 바꾸어 주는데 O(n)만큼의 시간이 걸립니다. 그러나 세그먼트 트리는 요소 한개당 O(logn) 만큼의 시간이 걸리므로, 더욱 빠릅니다.

 

1. 배열들을 만듭니다. 처음 초기값들을 담을 배열과, segment tree을 구성하기 위한 배열을 만들어 줍니다.

트리를 구성하기위한 배열의 크기는 요소들의 개수 * 4 만큼 만들어 줍니다. (2의 제곱수인 경우는 트리의 개수는 2*n-1, 그 외의 경우는 2*( [lg n]+1) -1 입니다,    n*4는 앞의 두 경우보다 더 크기 때문에, 트리의 공간이 부족할 이유가 없습니다)

 

물론 n의 최댓값이 1000000이므로, 정적 배열을 만들 때는 1000000, 4000000 으로 만듭니다.

 

2. 세그먼트 트리를 초기화 합니다. (트리에 누적합이 들어 있습니다)

3. 1을 입력 받으면, 특정 요소를 원하는 것으로 바꾼 다음 관련된 tree의 값을 바꾸어주며, 

     2을 입력 받으면, 특정 범위내의 구간합을 구한 다음 출력합니다.

 

https://www.acmicpc.net/problem/2042

2042번: 구간 합 구하기