hdu-1166 敌兵布阵---树状数组模板

题目链接：

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

题目大意：

维护动态的区间和，单点更新，就是模板题

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<set>
 4 #include<cstring>
 5 #include<cstdio>
 6 using namespace std;
 7 const int maxn = 100000 + 10;
 8 typedef long long ll;
 9 int tree[maxn];
10 int n;
11 int lowbit(int x)
12 {
13     return x & (-x);
14 }
15 void add(int x, int d)
16 {
17     while(x <= n)
18     {
19         tree[x] += d;
20         x += lowbit(x);
21     }
22 }
23 ll sum(int x)
24 {
25     ll ret = 0;
26     while(x > 0)//此处等于0会导致无限循环
27     {
28         ret += tree[x];
29         x -= lowbit(x);
30     }
31     return ret;
32 }
33 int main()
34 {
35     int T, cases = 0;
36     scanf("%d", &T);
37     while(T--)
38     {
39         scanf("%d", &n);
40         memset(tree, 0, sizeof(tree));
41         int x, y;
42         for(int i = 1; i <= n; i++)
43         {
44             scanf("%d", &x);
45             add(i, x);
46         }
47         char s[8];
48         printf("Case %d:
", ++cases);
49         while(scanf("%s", s) && s[0] != 'E')
50         {
51             scanf("%d%d", &x, &y);
52             if(s[0] == 'A')
53             {
54                 add(x, y);
55             }
56             else if(s[0] == 'S')
57             {
58                 add(x, -y);
59             }
60             else if(s[0] == 'Q')
61             {
62                 ll ans = sum(y) - sum(x - 1);
63                 printf("%lld
", ans);
64             }
65         }
66     }
67 }