HDU 1166 敌兵布阵（线段树 or 二叉索引树）

http://acm.hdu.edu.cn/showproblem.php?pid=1166

题意：
第一行一个整数T，表示有T组数据。
每组数据第一行一个正整数N（N<=50000）,表示敌人有N个工兵营地，接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人（1<=ai<=50）。
接下来每行有一条命令，命令有4种形式：
(1) Add i j,i和j为正整数,表示第i个营地增加j个人（j不超过30）
(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人（j不超过30）;
(3)Query i j ,i和j为正整数,i<=j，表示询问第i到第j个营地的总人数;
(4)End 表示结束，这条命令在每组数据最后出现;

思路：

这道题目用线段树和二叉索引树都是可以做的，给出两种做法。

  1 #include<iostream>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5 
  6 const int maxn = 1 << 20;
  7 
  8 int n;
  9 
 10 struct node
 11 {
 12     int l, r;
 13     int num;
 14 }tree[maxn];
 15 
 16 char s[6];
 17 int ans;
 18 
 19 void build_tree(int l,int r,int k)
 20 {
 21     tree[k].l = l;
 22     tree[k].r = r;
 23     tree[k].num = 0;
 24 
 25     if(l==r)   return;
 26 
 27     int mid = (l + r) / 2;
 28     build_tree(l, mid, 2 * k);
 29     build_tree(mid + 1, r, 2 * k + 1);
 30 }
 31 
 32 void insert(int x, int i, int k)
 33 {
 34     if (tree[k].l == tree[k].r && tree[k].l == i)
 35     {
 36         tree[k].num += x;
 37         return;
 38     }
 39     int mid = (tree[k].l + tree[k].r) / 2;
 40     if (i <= mid)  insert(x, i, 2 * k);
 41     else           insert(x, i, 2 * k + 1);
 42     tree[k].num = tree[2 * k].num + tree[2 * k + 1].num;
 43 }
 44 
 45 
 46 void search(int l,int r,int k)
 47 {
 48     if (tree[k].l == l && tree[k].r == r)
 49     {
 50         ans += tree[k].num;
 51         return;
 52     }
 53     int mid = (tree[k].l + tree[k].r) / 2;
 54     if (r <= mid)      search(l, r, 2 * k);
 55     else if(l > mid)   search(l, r, 2 * k + 1);
 56     else
 57     {
 58         search(l, mid, 2 * k);
 59         search(mid + 1, r, 2 * k + 1);
 60     }
 61 }
 62 
 63 int main()
 64 {
 65     //freopen("D:\\txt.txt", "r", stdin);
 66     int T;
 67     scanf("%d", &T);
 68     int x, y;
 69     int kase = 0;
 70     while (T--)
 71     {
 72         scanf("%d", &n);
 73         build_tree(1, n, 1);
 74         int a;
 75         for (int i = 1; i <= n; i++)
 76         {
 77             cin >> a;
 78             insert(a, i, 1);
 79         }
 80         printf("Case %d:\n", ++kase);
 81         while (scanf("%s",&s) && s[0] != 'E')
 82         {
 83             scanf("%d%d", &x, &y);
 84             if (s[0] == 'Q')
 85             {
 86                 ans = 0;
 87                 search(x, y, 1);
 88                 cout << ans << endl;
 89             }
 90             else if (s[0] == 'A')
 91             {
 92                 insert(y, x, 1);
 93             }
 94             else
 95             {
 96                 insert(-y, x, 1);
 97             }
 98         }
 99     }
100 }

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 const int maxn = 50000 + 5;
 7 
 8 int c[maxn];
 9 int n;
10 char s[6];
11 
12 int lowbit(int x)
13 {
14     return x&-x;
15 }
16 
17 int sum(int x)
18 {
19     int num = 0;
20     while (x > 0)
21     {
22         num += c[x];
23         x -= lowbit(x);
24     }
25     return num;
26 }
27 
28 void add(int x, int d)
29 {
30     while (x <= n)
31     {
32         c[x] += d;
33         x += lowbit(x);
34     }
35 }
36 
37 int main()
38 {
39     //freopen("D:\\txt.txt", "r", stdin);
40     int T;
41     scanf("%d", &T);
42     int x, y;
43     int kase = 0;
44     while (T--)
45     {
46         memset(c, 0, sizeof(c));
47         cin >> n;
48         int a;
49         for (int i = 1; i <= n; i++)
50         {
51             cin >> a;
52             add(i, a);
53         }
54         printf("Case %d:\n", ++kase);
55         while (scanf("%s",&s) && s[0] != 'E')
56         {
57             scanf("%d%d", &x, &y);
58             if (s[0] == 'Q')
59             {
60                 cout << sum(y) - sum(x - 1) << endl;
61             }
62             else if (s[0] == 'A')
63             {
64                 add(x, y);
65             }
66             else
67             {
68                 add(x, -y);
69             }
70         }
71     }
72 }

HDU 1166 敌兵布阵（线段树 or 二叉索引树）

推荐阅读