펜윅트리(이진 인덱스트리 : Binary Index Tree)

#include<iostream>
using namespace std;
typedef long long ll;
int N, M, K;
ll A[1000005], tree[1000005];
void update(int idx, ll diff) {
    while (idx <= N) {
        tree[idx] += diff;
        idx += (idx & -idx);
    }
}
ll sumQ(int idx) {
    ll ans = 0;
    while (idx > 0) {
        ans += tree[idx];
        idx -= (idx & -idx);
    }
    return ans;
}
int main() {
    scanf("%d%d%d", &N, &M, &K);
    for (int i = 1; i <= N; i++) {
        scanf("%lld", &A[i]);
        update(i, A[i]);
    }
    for (int i = 0; i < M + K; i++) {
        ll a;
        scanf("%lld", &a);
        if (a == 1) {
            int b; ll c;
            scanf("%d%lld", &b, &c);
            ll diff = c - A[b];
            A[b] = c;
            update(b, diff);
        }
        else if (a == 2) {
            int b, c;
            scanf("%d%d", &b, &c);
            printf("%lld\n", sumQ(c) - sumQ(b-1));
        }
    }
    return 0;
}