백준 2042번 구간합 구하기 C++

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

일반적인 구간합 구하기 문제라면, 배열을 별도로 두고 특정 인덱스까지 구간합을 저장해서 구하겠지만,

이 문제의 경우처럼 원소 자체가 빈번하게 업데이트 되면서 구간합을 구해야 한다면 인덱스 트리를 사용하는 게 편리하다.

인덱스 트리를 만드는 과정은 다음과 같다.

우선 leaf가 꽉 찬 트리로 만들어야 하기 때문에 원소의 개수보다 큰 가장 작은 2의 제곱수를 찾는다.

가령 예시의 경우처럼 원소가 5개라면 5보다 큰 가장 작은 2의 제곱수는 8이다.

기본적으로 배열은 1-indexed로 한다. 따라서 leaf에 처음 숫자들이 저장될 텐데, 인덱스 8부터 들어가면 된다.

비는 공간은 쿼리와 상관없는 수로 채워준다. (구간합 구하기 문제 같은 경우 0은 합에 영향을 미치지 않기 때문에 0으로 채워준다)

(가령 구간의 최댓값을 저장하는 인덱스 트리라면 구간의 최댓값에 영향을 미치지 않게 가장 작은 수로 비는 부분을 채워주면 된다)

인덱스를 찾았으니 구간합을 채워주면 된다.

부모의 인덱스는 자식 인덱스 /2, 왼쪽 자식은 부모 인덱스 *2, 오른쪽은 *2 +1 이라는 것을 이용해서 쿼리를 만들어주면 된다.

#include<iostream>
#define MAX 1000002
using namespace std;
 
typedef long long ll;
ll idxTree[4 * MAX];
 
void Update(int idx, ll delta) {
    while (idx > 0) {
        idxTree[idx] += delta;
        idx /= 2;
    }
}
 
ll findSum(int st, int en) {
    ll ret = 0;
    while (st <= en) {
        if (st % 2 == 1) ret += idxTree[st];
        if (en % 2 == 0) ret += idxTree[en];
        st = (st + 1) / 2;
        en = (en - 1) / 2;
    }
    return ret;
}
 
int main(void) {
    int n, m, k;
    cin >> n >> m >> k;
    int start = 1;
    while (start < n) {
        start *= 2; //n보다 큰 가장 작은 2의 제곱수
    }
    
    for (int i = 0; i < n; i++) { //원래 빈공간도 채워줘야 한다. 쿼리에 영향을 받지 않는 값으로
        cin >> idxTree[start + i];
    }
    //트리의 아래에서 위로 채워가기
    for (int i = start - 1; i >= 1; i--) {
        idxTree[i] = idxTree[2 * i] + idxTree[2 * i + 1];
    }
    for (int i = 0; i < m + k; i++) {
        int a, b, c;
        cin >> a >> b >> c; //두 경우 모두 인덱스를 계산해서 넘겨야함, 차이는 새거-있던거
        if (a == 1) Update(b + start - 1, c - idxTree[b + start - 1]);
        else if (a == 2) cout << findSum(b + start - 1, c + start - 1) << '\n';
    }
    return 0;
}