[백준] 구간 합 구하기 2042번 (c++) 세그먼트트리

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

 

풀이 방법

 

구간 합을 구하고, 요소를 변경하고 구간 합을 또 구하니 세그먼트 트리를 사용하면 된다.

 

세그먼트트리 구현 시 주의점

1. 세그먼트트리의 인덱스는 1부터 시작한다.
2. node와 배열의 idx는 다르다
3. build함수 구현시 start == end일 때 tree [node] = arr [start]이다.
4. update를 할 때 원래 배열값과 차이인 diff값으로 업데이트를 진행한다.
5. tree의 노드의 수는 일반적으로 n * 4로 잡는다.

#include <iostream>

using namespace std;

int n, m, k;
long long arr[1000001];
long long tree[4000004];

long long build(int start, int end, int node) { // 트리 노드 빌드
    if (start == end) return tree[node] = arr[start]; // arr[node]가 아니라 arr[start]이다.
                        //리턴을 해주어야 한다.
    int mid = (start + end) / 2;

    return tree[node] = build(start, mid, node * 2) + build(mid+1, end, node * 2 + 1);
}

void update(int start, int end, int node,int idx, long long diff) {
    if (start > idx || end < idx) return ; // node가 아니라 idx이다.

    tree[node] +=  diff;

    if (start == end) return;

    int mid = (start + end) / 2;
    update(start, mid, node * 2, idx, diff);
    update(mid + 1, end, node * 2 + 1, idx, diff);
    return ;
}

long long sum(int start, int end, int node, int left, int right) {
    // 범위가 벗어난 경우
    if (start > right || end < left) return 0;

    //포함 되는 경우 
    if (left <= start && end <= right) return tree[node];

    int mid = (start + end) / 2;
    return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right);
}
int main() {
    cin >> n >> m >> k;

    for (int i = 1;i <= n;i++) {
        cin >> arr[i];
    }
    build(1, n, 1);
    int a, b;
    long long c;
    for (int i = 0;i < m + k;i++) {
        cin >> a >> b >> c;
        if (a == 1) {
            long long diff = c - arr[b];
            arr[b] = c;
            update(1, n, 1, b, diff);
        }
        else {
            cout << sum(1, n, 1, b, c) << endl;
        }
    }
    return 0;
}