//  [7/24/2014 Sjm]/*第一道用线段树做的题，照着大神的代码风格写的，，就当作线段树单点更新的模板吧。。。。(当年用树状数组做的：)*/

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7 #define lson l, m, rt << 1 8 #define rson m + 1, r, rt << 1 | 1 9 #define GetMid l + ((r-l) >> 1)10 11 const int MAX = 50005;12 int sum[MAX << 2];13 14 void PushUp(int rt) { sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; }15 16 void Build(int l, int r, int rt) {17     if (l == r) { scanf("%d", &sum[rt]); return; }18     int m = GetMid;19     Build(lson);20     Build(rson);21     PushUp(rt);22 }23 24 void Update(int pos, int add, int l, int r, int rt) {25     if (l == r) { sum[rt] += add; return; }26     int m = GetMid;27     if (pos <= m) { Update(pos, add, lson); }28     else { Update(pos, add, rson); }29     PushUp(rt);30 }31 32 int Query(int L, int R, int l, int r, int rt) {33     if (L <= l && r <= R) { return sum[rt]; }34     int ret = 0;35     int m = GetMid;36     if (L <= m) { ret += Query(L, R, lson); }37     if (R > m) { ret += Query(L, R, rson); }38     return ret;39 }40 41 int main()42 {43     //freopen("input.txt", "r", stdin);44     int T, N, a, b;45     scanf("%d", &T);46     for (int cas = 1; cas <= T; ++cas) {47         printf("Case %d:\n", cas);48         scanf("%d", &N);49         Build(1, N, 1);50         char str[10];51         while (scanf("%s", str) && 'E' != str[0]) {52             scanf("%d %d", &a, &b);53             if ('Q' == str[0]) { printf("%d\n", Query(a, b, 1, N, 1)); }54             else {55                 if ('A' == str[0]) { Update(a, b, 1, N, 1); }56                 else { Update(a, -b, 1, N, 1); }57             }58         }59     }60     return 0;61 }