【题意】：给出n个兵营，每个兵营初始都有一定数量的士兵，兵营的士兵数量会改变，不定时查询第i个兵营到第j个兵营的士兵数量，输出每次询问的结果。(n <= 50000)
【题解】：很简单的一道数据结构题目。
这种题目如果能用树状数组最好就用，因为树状数组太容易写了。
最近在学线段树，所以两种版本的都写了一次。
【代码】：
【树状数组】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 using namespace std;
8 #define pb push_back
9 #define maxn 50005
10 #define lowbit(x) (x & (-x))
11 int val[maxn], n;
12
13 void add(int x, int e) {
14 for(int i = x; i < maxn; i += lowbit(i)) {
15 val[i] += e;
16 }
17 }
18
19 int sum(int x) {
20 int res = 0;
21 for(int i = x; i; i -= lowbit(i)) {
22 res += val[i];
23 }
24 return res;
25 }
26
27 int main() {
28 int T, Case = 1, e, a, b;
29 char str[10];
30 scanf("%d", &T);
31 while(T--) {
32 scanf("%d", &n);
33 memset(val, 0, sizeof(val));
34 for(int i = 1; i <= n; i++) {
35 scanf("%d", &e);
36 add(i, e);
37 }
38 printf("Case %d:\n", Case++);
39 while(1) {
40 scanf("%s", str);
41 if(str[0] == 'E') break;
42 else {
43 scanf("%d%d", &a, &b);
44 if(str[0] == 'Q') printf("%d\n", sum(b) - sum(a - 1));
45 else if(str[0] == 'A') add(a, b);
46 else add(a, -b);
47 }
48 }
49 }
50 return 0;
51 }
【线段树】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 using namespace std;
8 #define pb push_back
9 #define lc(x) (x << 1)
10 #define rc(x) (x << 1 | 1)
11 #define MAX 50005
12 int seg[MAX<<2];
13 int n;
14 void pushup(int p) {
15 seg[p] = seg[lc(p)] + seg[rc(p)];
16 }
17
18 void build(int l, int r, int p) {
19 if(l == r) {
20 scanf("%d", &seg[p]);
21 return;
22 }
23 int mid = (l + r) >> 1;
24 build(l, mid, lc(p));
25 build(mid + 1, r, rc(p));
26 pushup(p);
27 }
28
29 int query(int L, int R, int l, int r, int p) {
30 if(L == l && R == r) return seg[p];
31 int mid = (l + r) >> 1;
32 if(L > mid) return query(L, R, mid + 1, r, rc(p));
33 else if(R <= mid) return query(L, R, l, mid, lc(p));
34 else return query(L, mid, l, mid, lc(p)) + query(mid + 1, R, mid + 1, r, rc(p));
35 }
36
37 void update(int x, int val, int l, int r, int p) {
38 if(l == r) {
39 seg[p] += val;
40 return;
41 }
42 int mid = (l + r) >> 1;
43 if(x <= mid) update(x, val, l, mid, lc(p));
44 else update(x, val, mid + 1, r, rc(p));
45 pushup(p);
46 }
47
48 int main() {
49 int T, Case = 1, a, b;
50 char str[10];
51 scanf("%d", &T);
52 while(T--) {
53 scanf("%d", &n);
54 build(1, n, 1);
55 printf("Case %d:\n", Case++);
56 while(1) {
57 scanf("%s", str);
58 if(str[0] == 'E') break;
59 else {
60 scanf("%d%d", &a, &b);
61 if(str[0] == 'Q') printf("%d\n", query(a, b, 1, n, 1));
62 else if(str[0] == 'A') update(a, b, 1, n, 1);
63 else update(a, -b, 1, n, 1);
64 }
65 }
66 }
67 return 0;
68 }