树状数组

#include<iostream>
using namespace std;
const int N=100010;
int a[N],tr[N];//树状数组表示的是(N-2^k,N]的和（k的含义与下面相同），可通过递归，将树状数组转化为前缀和数组
int n,m;
int lowbit(int x)//lowbit返回的是2的k次方，k为x二进制表示末尾连续0的个数。
{
    return x&-x;
}
int query(int x)
{
    int res=0;
    for(int j=x;j;j-=lowbit(j))
    {
        res+=tr[j];
    }
    return res;
}
void add(int st,int x)
{
    for(int j=st;j<=n;j+=lowbit(j))
    {
        tr[j]+=x;
    }
}
int main()
{
   
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        add(i,a[i]);
    }
    while(m--)
    {
        int q,k,p;
        cin>>k>>q>>p;
        if(k==0){
            cout<<query(p)-query(q-1)<<endl;
    }
        else {
            add(q,p);
        }
    }
}