树状数组（模板）

参考博客
题目： P3374 【模板】树状数组 1

lowbit：二进制最低位1的大小，也是其能管辖到的数的范围
树状数组记得开long long 
单次操作的时间复杂度是O(lgn)
只需开N的空间
比线段树的常数小
按值建树（ add(a[i],1) ）：ask可以求比当前数小（或大）的数的数量
按位置建树（ add(pos,1) ）：ask可以求当前点左（或右）边的点数
树状数组：求前面或后面有多少个数
         求某区间特定性质点的数量
可用于单点修改，区间查询
      区间修改，单点查询等等

//

#include<bits/stdc++.h>
using namespace std;
#define low(x) x&(-x)
#define ll long long 
int const N=5e5+7;
int n,m;
ll a[N];   //tr[N]  //树状数组
void add(int pos,int val){  //维护其前缀和的操作
    for(;pos<=n;pos+=low(pos)){   //记住就好
        a[pos]+=val;
    }
}
ll ask(int x){  //查询x的前缀和
    ll z=0;
    for(;x;x-=low(x)){  //记住就好
        z+=a[x];
    }
    return z;
}
int main(){
    cin >> n >> m;
    for(int i=1;i<=n;++i){
        int b;
        cin >> b;
        add(i,b);
    }
    while(m--){
        int b,c,d;
        cin >> b >> c >> d;
        if(b==1) add(c,d);
        else cout << ask(d)-ask(c-1) << endl;
    }
    return 0;
}