1 /*
2 线段树基本功能：区间值的和，修改某个值
3 */
4 #include <cstdio>
5 #include <cstring>
6 #define lson l, m, rt << 1
7 #define rson m+1, r, rt << 1|1
8
9 const int MAX_N = 50000 + 10;
10 int sum[MAX_N<<2];
11
12 void pushup(int rt) //杭电大牛：notOnlySuccess 版本
13 {
14 sum[rt] = sum[rt<<1] + sum[rt<<1|1];
15 }
16
17 void build(int l, int r, int rt)
18 {
19 if (l == r)
20 {
21 scanf ("%d", &sum[rt]);
22 return ;
23 }
24 int m = (l + r) >> 1;
25 build (lson);
26 build (rson);
27 pushup (rt);
28 }
29
30 void update(int p, int add, int l, int r, int rt)
31 {
32 if (l == r)
33 {
34 sum[rt] += add;
35 return ;
36 }
37 int m = (l + r) >> 1;
38 if (p <= m) update (p, add, lson);
39 else update (p, add, rson);
40 pushup (rt);
41 }
42
43 int query(int ql, int qr, int l, int r, int rt)
44 {
45 if (ql <= l && r <= qr)
46 {
47 return sum[rt];
48 }
49 int m = (l + r) >> 1;
50 int ans = 0;
51 if (ql <= m) ans += query (ql, qr, lson);
52 if (qr > m) ans += query (ql, qr, rson);
53
54 return ans;
55 }
56
57 int main(void) //HDOJ 1166 敌兵布阵
58 {
59 //freopen ("inA.txt", "r", stdin);
60 int t, n, cas, ans;
61 int b, c;
62 char s[10];
63
64 while (~scanf ("%d", &t))
65 {
66 cas = 0;
67 while (t--)
68 {
69 scanf ("%d", &n);
70 build (1, n, 1);
71 printf ("Case %d:
", ++cas);
72 while (~scanf ("%s", &s))
73 {
74 if (strcmp (s, "End") == 0) break;
75 scanf ("%d%d", &b, &c);
76 if (strcmp (s, "Query") == 0)
77 {
78 ans = query (b, c, 1, n, 1);
79 printf ("%d
", ans);
80 }
81 else if (strcmp (s, "Add") == 0)
82 {
83 update (b, c, 1, n, 1);
84 }
85 else if (strcmp (s, "Sub") == 0)
86 {
87 update (b, -c, 1, n, 1);
88 }
89 }
90 }
91 }
92
93 return 0;
94 }
1 /*
2 树状数组
3 */
4 #include <cstdio>
5 #include <cstring>
6
7 const int MAX_N = 50000 + 10;
8 int a[MAX_N];
9 int n, num;
10
11 int lowbit(int t) //求 2^k
12 {
13 //return t & (t ^ (t - 1));
14 return t & (-t);
15 }
16
17 void plus(int num, int x) //第i个增加num个人
18 {
19 while (x <= n)
20 {
21 a[x] += num;
22 x += lowbit (x);
23 }
24 }
25
26 int sum(int x) //求前x项的和
27 {
28 int sum = 0;
29 while (x > 0)
30 {
31 sum += a[x];
32 x -= lowbit(x);
33 }
34 return sum;
35 }
36
37 int main(void)
38 {
39 //freopen ("inA.txt", "r", stdin);
40
41 int t;
42 char op[100];
43
44 scanf ("%d", &t);
45 int k = t;
46
47 while (k--)
48 {
49 memset (a, 0, sizeof (a));
50 scanf ("%d", &n);
51 for (int i=1; i<=n; ++i)
52 {
53 scanf ("%d", &num);
54 plus (num, i);
55 }
56 int r = 1;
57 while (scanf ("%s", &op), op[0] != 'E')
58 {
59 int a, b;
60 scanf ("%d%d", &a, &b);
61 switch (op[0])
62 {
63 case 'A':
64 plus (b, a);
65 break;
66 case 'S':
67 plus (-b, a);
68 break;
69 case 'Q':
70 if (r)
71 printf ("Case %d:
", t - k);
72 r = 0;
73 printf ("%d
", sum (b) - sum (a-1));
74 break;
75 }
76 }
77 }
78
79 return 0;
80 }
树状数组