HDU 1166 敌兵布阵 树状数组

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 typedef long long LL;
 8 
 9 const int maxn = 5e4+10;
10 
11 int sum[maxn];
12 int n;
13 
14 void init() {
15     memset(sum, 0, sizeof(sum));
16 }
17 
18 void add(int p, int v) {
19     while (p < maxn) {
20         sum[p] += v;
21         p += p&-p;
22     }
23 }
24 
25 int get_sum(int p) {
26     int ret = 0;
27     while (p > 0) {
28         ret += sum[p];
29         p -= p&-p;
30     }
31     return ret;
32 }
33 
34 int main() {
35     int T,kase=0;
36     scanf("%d", &T);
37     while (T--) {
38         init();
39         scanf("%d", &n);
40         for (int i = 1; i <= n; i++) {
41             int x;
42             scanf("%d", &x);
43             add(i, x);
44         }
45         printf("Case %d:
", ++kase);
46         char cmd[11];
47         while (scanf("%s", cmd) == 1&&cmd[0]!='E') {
48             if (cmd[0] == 'Q') {
49                 int l, r;
50                 scanf("%d%d", &l, &r);
51                 printf("%d
", get_sum(r) - get_sum(l - 1));
52             }
53             else if (cmd[0] == 'A') {
54                 int p, v;
55                 scanf("%d%d", &p, &v);
56                 add(p, v);
57             }
58             else if (cmd[0] == 'S') {
59                 int p, v;
60                 scanf("%d%d", &p, &v);
61                 add(p, -v);
62             }
63         }
64     }
65     return 0;
66 }