백준 1275 커피숍2 C++

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

수열의 성분이 빈번하게 바뀌면서, 구간합을 물어보는 문제이기 때문에 인덱스 트리를 구현해주면 된다.

인덱스 트리에 대한 좀 더 자세한 설명은 https://hugssy.tistory.com/132 를 참고하면 된다.

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll idxTree[4 * 100002];
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;
}
void Update(int idx, ll delta) {
    while (idx > 0) {
        idxTree[idx] += delta;
        idx /= 2;
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int n, q;
    cin >> n >> q;
 
    int start = 1;
    while (start < n)
        start *= 2; //n보다 큰 가장 작은 2의 제곱수
 
    for (int i = 0; i < n; i++)
        cin >> idxTree[i + start];
 
    for (int i = start - 1; i >= 1; i--)
        idxTree[i] = idxTree[2 * i] + idxTree[2 * i + 1];
 
    while (q--) {
        int x, y, a, b;
        cin >> x >> y >> a >> b;
        if (x > y) swap(x, y);
        cout << findSum(x + start - 1, y + start - 1) << '\n';
        Update(a + start - 1, b - idxTree[a + start - 1]);
    }
    return 0;
}