线段树 




 1 #include <cstdio> 2 #include <iostream> 3 using namespace std; 4 #define N 200010 5 int sum[N]; 6 void build(int l,int r,int root){ 7     if(l==r)scanf("%d",&sum[root]); 8     else { 9         int mid=(l+r)/2;10         build(l,mid,root*2);11         build(mid+1,r,root*2+1);12         sum[root]=sum[root*2]+sum[root*2+1];13     }14 }15 void add(int i,int j,int l,int r,int root){16     if(l==r)sum[root]+=j;17     else {18         int mid=(r+l)/2;19         if(i<=mid)add(i,j,l,mid,root*2);20         else add(i,j,mid+1,r,root*2+1);21         sum[root]=sum[root*2]+sum[root*2+1];22     }23 }24 void query(int x,int y,int l,int r,int root,int &a){25     if(x<=l&&y>=r){26          a+=sum[root];27          return;28     }29     int mid=(r+l)/2;30     if(x<=mid)query(x,y,l,mid,root*2,a);31     if(y>mid)query(x,y,mid+1,r,root*2+1,a);32 }33 int main(){34     freopen("test.txt","r",stdin);35     int t,n,q,x,y,case1=0;36     char s[7];37     scanf("%d",&t);38     while(t--){39         case1++;40         printf("Case %d:\n",case1);41         scanf("%d",&n);42         build(1,n,1);43         while(scanf("%s",s)!=EOF){44             if(s[0]==‘E‘)break;45             scanf("%d%d",&x,&y);46             switch (s[0]){47                 case ‘Q‘:q=0;query(x,y,1,n,1,q);printf("%d\n",q);break;48                 case ‘A‘:add(x,y,1,n,1);break;49                 case ‘S‘:add(x,-y,1,n,1);break;50             }51         }52     }53     return 0;54 }