树状数组

#include <iostream>
#define N 500010
using namespace std;
int a[N];
int c[N];
int n;

int lowbit(int x) {
    return x & (-x);
}

void update (int i,int val) {
    while (i <= n) {
        c[i] += val;
        i += lowbit(i);
    }
}

int sum(int i) {
    int ans = 0;
    while(i > 0) {
        ans += c[i];
        i -= lowbit(i);
    }
    return ans;
}

int main() {
    int m; cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) {
        for(int j = i-lowbit(i)+1; j <= i; j++) {
            c[i] += a[j];
        }
    }
    while(m--) {
        int op,x,y; cin >> op >> x >>y;
        if(op == 1) {
            update(x,y);
        } else if(op == 2) {
            cout << sum(y) - sum(x-1) << endl;
        }
    }
    return 0;
}