1 #define lson l, m, rt<<1 2 #define rson m+1, r, rt<<1|1   3 int sum[500005]; 4 void pushup(int rt) 5 { 6     sum[rt]=sum[rt<<1]+sum[rt<<1|1]; 7 } 8 void build(int l, int r, int rt) 9 {10     if(l==r)11     {12         scanf("%d", &sum[rt]);13         return ;14     }15     int m=(l+r)>>1;16     build(lson);17     build(rson);18     pushup(rt);19 }20 void update(int p, int add, int l, int r, int rt)21 {22     if(l==r)23     {24         sum[rt]+=add;25         return ;26     }27     int m=(l+r)>>1;28     if(p<=m)29         update(p, add, lson);30     else31         update(p, add, rson);32     pushup(rt);33 }34 int query(int L, int R, int l, int r, int rt)35 {36     if(L<=l && r<=R)37         return sum[rt];38     int m=(l+r)>>1;39     int ret=0;40     if(L<=m)41         ret+=query(L, R, lson);42     if(R>m)43         ret+=query(L, R, rson);44     return ret;45 }46 int main()47 {48 #ifndef ONLINE_JUDGE49     freopen("in.txt", "r", stdin);50     freopen("out.txt", "w", stdout);51 #endif52     int t, n, ca=1;53     int a, b;54     scanf("%d", &t);55     while(t--)56     {57         printf("Case %d:\n", ca++);58         scanf("%d", &n);59         build(1, n, 1);60         char op[10];61         while(~scanf("%s", op))62         {63             if(strcmp(op, "End")==0)64                 break;65             scanf("%d%d", &a, &b);66             if(strcmp(op, "Query")==0)67                 printf("%d\n", query(a, b, 1, n, 1));68             else if(strcmp(op, "Sub")==0)69                 update(a, -b, 1, n, 1);70             else71                 update(a, b, 1, n, 1);72         }73     }74     return 0;75 }