（模板）树状数组
树下
2018-10-29 19:56:26
```
#include<bits/stdc++.h>
const int maxn=500001;
using namespace std;
int n,m,a[maxn],c[maxn],flag,ta,tb;
int lowbit(int x){
return x&(-x);
}
void update(int x,int num)
{
if(x>n)
return ;
c[x]+=num;
update(x+lowbit(x),num);
}
int getsum(int x)
{
if(!x) return 0;
return getsum(x-lowbit(x))+c[x];
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
update(i,a[i]);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&flag,&ta,&tb);
if(flag==1)update(ta,tb);
else
printf("%d\n",getsum(tb)-getsum(ta-1));
}
}
```