[백준] 2042 구간 합 구하기

문제 주소 : www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

문제 확인

 

세그먼트 트리를 활용하면 쉽게 풀 수 있는 문제입니다.

세그먼트 트리 : latter2005.tistory.com/28

[자료구조] 세그먼트 트리

수 변경은 구간이 아닌 단일 숫자에서 일어나므로 Lazy propagation을 사용할 필요 없습니다.

 

풀이

 

세그먼트 트리를 작성하고 출력 쿼리는 같은 방식으로 출력하면 됩니다.

b번째 숫자를 c로 변경하는 방법은 b번째 숫자가 저장되어 있는 배열의 인덱스는 tree[b + n - 1]이므로 이를 c로 변경한 후 트리에 반영해 주면 됩니다.

tree[b + n - 1]의 부모 노드는 tree[(b + n - 1)/2]이므로 c로 변경했을 때 차이만큼 반영해 주면 됩니다. 이를 루트 노드까지 반복해 주면 모든 트리에 반영이 됩니다.

 

코드

#include <cstdio>
using namespace std;
 
int main() {
    long long n, m, k;
    long long tree[2000002];
    scanf("%lld%lld%lld", &n, &m, &k);
    for (int i = 0; i < n; i++)
        scanf("%lld", &tree[n + i]);
    for (int i = n - 1; i > 0; i--)
        tree[i] = tree[i << 1] + tree[i << 1 | 1];
    for (int i = 0; i < m + k; i++) {
        long long a, b, c;
        scanf("%lld%lld%lld", &a, &b, &c);
        if (a == 1) {
            b += n - 1;
            long long gap = c - tree[b];
            tree[b] = c;
            for (b >>= 1; b >= 1; b >>= 1) {
                tree[b] += gap;
            }
        }
        else {
            long long sum = 0;
            for (b += n - 1, c += n; b < c; b >>= 1, c >>= 1) {
                if (b & 1) sum += tree[b++];
                if (c & 1) sum += tree[--c];
            }
            printf("%lld\n", sum);
        }
    }
}