1 #include<stdio.h>
  2 #include<string.h>
  3 int value[200005];
  4 struct NODE{
  5     NODE *lchild,*rchild;
  6     int left,right;
  7     int sum;
  8 }mem[100001];
  9 int mempos=0;
 10 NODE *makenode()
 11 {
 12     NODE *p=&mem[mempos++];
 13     memset(p,0,sizeof(p));
 14     return p;
 15 }
 16 void update(NODE *root,int id)
 17 {
 18     if(root->right-root->left==1&&(id==root->right||id==root->left))
 19     {
 20         root->sum=value[root->right]+value[root->left];
 21     }else
 22     {
 23         int mid=(root->left+root->right)/2;
 24         if(id>=mid)
 25         update(root->rchild,id);
 26         if(id<=mid)
 27         update(root->lchild,id);
 28         root->sum=root->rchild->sum+root->lchild->sum-value[mid];
 29     }
 30 }
 31 NODE *build(int beg,int end)
 32 {
 33     NODE * root=makenode();
 34     root->left=beg;
 35     root->right=end;
 36     if(end-beg==1)
 37     {
 38         root->sum=value[beg]+value[end];
 39     }else 
 40     {
 41         int mid=(beg+end)/2;
 42         root->lchild=build(beg,mid);
 43         root->rchild=build(mid,end);
 44         root->sum=root->rchild->sum+root->lchild->sum-value[mid];
 45     }
 46     return root;
 47 }
 48 int get(NODE *root,int beg,int end)
 49 {
 50     if(root->left==beg&&root->right==end)
 51     {
 52         return root->sum;
 53     }
 54         int mid=(root->left+root->right)/2;
 55         if(beg>=mid)
 56         {
 57             return get(root->rchild,beg,end);
 58         }else if(end<=mid)
 59         {
 60             return get(root->lchild,beg,end);
 61         }else 
 62         {
 63             int l=get(root->lchild,beg,mid);
 64             int r=get(root->rchild,mid,end);
 65              return l+r-value[mid];
 66         }
 67 }
 68         
 69 int main()
 70 {
 71     int t,n,i,j,k,ss;
 72     int a,b;
 73     int co;
 74     char qus[20];
 75     scanf("%d",&t);
 76         for(co=1;co<=t;co++)
 77         {
 78             printf("Case %d:\n",co);
 79             scanf("%d",&n);
 80             for(i=1;i<=n;i++)
 81             {
 82                 scanf("%d",&value[i]);
 83             }
 84             getchar();
 85             mempos=0;
 86             NODE *root=build(1,n);
 87             while(scanf("%s",qus))
 88             {
 89                 if(strcmp(qus,"End")==0)
 90                 {
 91                     break;
 92                 }
 93                 if(strcmp(qus,"Add")==0)
 94                 {
 95                     scanf("%d%d",&a,&b);
 96                     value[a]+=b;
 97                     update(root,a);
 98                 }
 99                 if(strcmp(qus,"Sub")==0)
100                 {
101                     scanf("%d%d",&a,&b);
102                     value[a]-=b;
103                     update(root,a);
104                 }
105                 if(strcmp(qus,"Query")==0)
106                 {
107                     scanf("%d%d",&a,&b);
108                     ss=get(root,a,b);
109                     printf("%d\n",ss);
110                 }
111             }
112         }
113     
114 }
115 //写了一下午，终于用线段树写出了1166~