树状数组（BIT）

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
const int maxn = 1e6 + 10;
#define int long long
int bit[maxn];
int n, q;
int lowbit(int i){
    return i&(-i);
}
long long getsum(int i){   //bit[1]+...+bit[i]  前缀和
    long long res = 0;
    while (i >0 ){
        res += bit[i];
        i -= lowbit(i);
    }
    return res;
}
void add(int i, int x){    //在bit[i]上加上x
    while (i <=n){
        bit[i] += x;
        i += lowbit(i);
    }
}
int main()
{
    cin >> n >> q;    //n和数，q次查询
    int z;
    for (int i = 1; i <= n; i++){
        cin >> z;
        add(i,z);
    }
    int a,b,c;
    while (q--){
        
        cin >> a >> b >> c;
        if (a == 1){
            add(b,c);
        }
        else if(a == 2){
            cout << getsum(c)-getsum(b-1) << endl;
        }
    }
    return 0;
}