[백준 2042] 구간 합 구하기

 

 세그먼트 트리 문제이다. 어제의 문제와 같은 유형이기 때문에, 이제 보자마자 알 수 있었다. 대신 어제 푼 문제와 다른 점은 원본 배열이 중간중간 수정될 수 있다는 점인데, 이 때문에 트리를 update하는 함수를 따로 구현해 주었다.

 그 외에 신경쓰였던 것은 입력으로 주어지는 모든 수의 범위가 long long int의 범위라는 것인데, 정답이 long long int의 범위를 보장하지만 이러면 구간 합을 구해내는 도중에 오버플로우가 나지 않을까 하는 점에서였다. 그런데 잘 생각해 보면 정답이 long long int의 범위를 보장하므로, 중간에 오버플로우가 나더라도 결국에 구간 합을 구해내면 답을 정상적으로 출력되겠구나 싶었다(오버플로우가 범위를 초과하는 순간 무식하게 임의의 쓰레기 값이 들어가는 게 아니니까).

 

 그 다음에는 단순히 세그먼트 트리를 구현하는 것이라서 크게 어려운 부분은 없었다. 재귀적으로 구간 합을 저장하는 트리를 만들고, 마찬가지로 재귀적으로 update 하는 함수와 구간 합을 가져오는 함수를 만들어 답을 출력했다. update 함수는 지정한 인덱스를 포함하고 있는 구간들에 대해 변화량 값을 더해서 업데이트하는 식으로 처리했는데, 생각나는 대로 구현했지만 잘 동작했다.

#include <iostream>
#include <vector>

using namespace std;

vector<long long> arrSumTree;
vector<long long> numArr;

long long makeTree(int l, int r, int ind) {
    if(l==r) {
        arrSumTree[ind] = numArr[l];
        return arrSumTree[ind];
    } else {
        int mid = (l+r)/2;
        arrSumTree[ind] = makeTree(l, mid, ind*2) + makeTree(mid+1, r, ind*2+1);
        return arrSumTree[ind];
    }
}

long long getArrSum(int l, int r, int ind, int lBound, int rBound) {
    if(l>rBound || r<lBound) return 0;
    if(l>=lBound && r<=rBound) return arrSumTree[ind];
    int mid = (l+r)/2;
    return getArrSum(l, mid, ind*2, lBound, rBound) + getArrSum(mid+1, r, ind*2+1, lBound, rBound);
}

void updateTree(int l, int r, int ind, int target, long long delta) {
    if(target<l || target>r) return;
    arrSumTree[ind] += delta;
    if(l==r) {
        return; 
    } else {
        int mid = (l+r)/2;
        updateTree(l, mid, ind*2, target, delta);
        updateTree(mid+1, r, ind*2+1, target, delta);
    }
}

void initSize(int n) {
    arrSumTree = vector<long long>(n*4);
    numArr = vector<long long> (n+1);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;
    initSize(n);

    for(int i=1; i<=n; i++) {
        cin >> numArr[i];
    }

    makeTree(1, n, 1);

    int a, b;
    long long c;

    for(int i=0; i<m+k; i++) {
        cin >> a >> b >> c;
        if(a==1) {
            updateTree(1, n, 1, b, c-numArr[b]);
            numArr[b] = c;
        } else {
            cout << getArrSum(1, n, 1, b, c) << "\n";
        }
    }
}