1 #include
2 #include
3 #define MAXN 50001
4 struct Node
5 {
6 int left,right;
7 int sum;
8 };
9 Node Tree[MAXN * 20];
10 int Num[MAXN];
11 int Builder(int root, int left, int right)
12 {
13 Tree[root].left = left;
14 Tree[root].right = right;
15 if(Tree[root].left == Tree[root].right){
16 return Tree[root].sum = Num[left];
17 }
18 int mid = (left + right) / 2;
19 int L = Builder(2 * root, left, mid);
20 int R = Builder(2 * root + 1, mid + 1, right);
21 return Tree[root].sum = L + R;
22 }
23 int Find(int root, int left, int right)
24 {
25 if(Tree[root].left > right || Tree[root].right < left){
26 return 0;
27 }
28 if(left <= Tree[root].left && Tree[root].right <= right){
29 return Tree[root].sum;
30 }
31 int L = Find(2 * root, left, right);
32 int R = Find(2 * root + 1, left, right);
33 return L + R;
34 }
35 int Update(int root, int pos, int val)
36 {
37 if(Tree[root].left > pos || Tree[root].right < pos){
38 return Tree[root].sum;
39 }
40 if(Tree[root].left == pos && Tree[root].right == pos){
41 return Tree[root].sum += val;
42 }
43 int L = Update(2 * root, pos, val);
44 int R = Update(2 * root + 1, pos, val);
45 return Tree[root].sum = L + R;
46 }
47 int main()
48 {
49 int i, j, t, n;
50 int pos, val, cas;
51 char c[11];
52 scanf("%d", &t);
53 cas = 1;
54 while(t--)
55 {
56 scanf("%d", &n);
57 for(i = 1; i <= n; i++){
58 scanf("%d", &Num[i]);
59 }
60 Builder(1, 1, n);
61 printf("Case %d:\n", cas++);
62 while(scanf("%s", c))
63 {
64 if(c[0] == ‘E‘)break;
65 scanf("%d%d", &pos, &val);
66 if(c[0] == ‘Q‘){
67 printf("%d\n", Find(1, pos, val));
68 }
69 if(c[0] == ‘A‘){
70 Update(1, pos, val);
71 }
72 if(c[0] == ‘S‘){
73 Update(1, pos, -val);
74 }
75 }
76 }
77 return 0;
78 }