- #include
- using namespace std;
- struct tree{
- int l,r,sum;
- }t[1000001];
- int a[1000001],n,p,x,y,m;
- inline void build(int root,int left,int right)
- {
- t[root].l=left;t[root].r=right;
- if(left==right){t[root].sum=a[left];return;}
- int child(root<<1),mid((left+right)>>1);
- build(child,left,mid);build(child+1,mid+1,right);
- t[root].sum=t[child].sum+t[child+1].sum;
- }
- inline int search(int root,int left,int right)
- {
- if((t[root].l>=left)&&(t[root].r<=right))
- return t[root].sum;
- if((t[root].r<left)||(t[root].l>right))
- return 0;
- int local_sum(0),child(root<<1);
- if(t[child].r>=left)
- local_sum+=search(child,left,right);
- if(t[child+1].l<=right)
- local_sum+=search(child+1,left,right);
- return local_sum;
- }
- inline void add(int root,int goal,int plus)
- {
- if(t[root].l==t[root].r)
- {
- t[root].sum+=plus;
- return;
- }
- int child(root<<1);
- if(goal<=t[child].r)
- add(child,goal,plus);
- else
- add(child+1,goal,plus);
- t[root].sum=t[child].sum+t[child+1].sum;
- }
- int main()
- {
- cin>>n>>m;
- for(int i=1;i<=n;i++)
- cin>>a[i];
- build(1,1,n);
- for(int i=0;i<m;i++)
- {
- cin>>p>>x>>y;
- if(p==1)
- add(1,x,y);
- else
- cout<<search(1,x,y)<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3304971.html