hdu1166：敌兵布阵（树状数组或线段树）

题目描述：

一堆废话不用看......

输入：

第一行一个整数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 表示结束，这条命令在每组数据最后出现;
每组数据最多有40000条命令

输出：

对第i组数据,首先输出“Case i:”和回车,
对于每个Query询问，输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。

Sample Input：

1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End

Sample Output

Case 1:
6
33
59


相信这是很多人写线段树的第一题，我本来也用这一道题来学习线段树，我在网上找了个人的博客：ACM！荣耀之路！网址 ：http://blog.csdn.net/libin56842
这个人感觉很厉害，搜题解的时候经常见到他，于是学习他的代码。交上去的确AC了，但是写完后发现这是树状数组而不是线段树。我的代码里有注释。
代码如下：

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <cstdio>
 5 #include <algorithm>
 6 #include <string>
 7 using namespace std;
 8 #define maxn 55555
 9 int sum[maxn<<2];//按位左偏一位相当于乘以2，偏移2位相当于乘以2的平方
10 void pushup (int rt)//上推，rt是该数在数组中的下标。
11 {
12     sum[rt]=sum[rt<<1]+sum[rt<<1|1];//tr<<1|1等价于tr/2+1;
13 }
14 void build (int l,int r,int rt)//建立树状数组：利用先左节点后右节点最后根节点的后续遍历，递归的去读入数据
15 {
16     if (l==r)
17     {
18         scanf("%d",&sum[rt]);//把数据读入到了最下层的数组中
19         return ;
20     }
21     int m=(l+r)>>1;
22     build(l,m,rt<<1);
23     build(m+1,r,rt<<1|1);
24     pushup(rt);
25 }
26 void update (int p,int add,int l,int r,int rt)
27 {
28     if (l==r)
29     {
30         sum[rt]+=add;
31         return;
32     }
33     int m=(l+r)>>1;
34     if (p<=m)
35     update(p,add,l,m,rt<<1);
36     else
37     update(p,add,m+1,r,rt<<1|1);
38     //上面几行是在找到更新点的位置
39     pushup(rt);//从最下层的点一层层的更新根节点
40 }
41 int query (int ll,int rr,int l,int r,int rt)//最后一个参数rt表示的是数在数组中的下标
42 {
43     if (ll<=l&&rr>=r)//表明找到最下层的单个元素
44     return sum[rt];
45 
46     int ret=0;
47     int m=(l+r)>>1;
48 
49     if (ll<=m)
50     ret+=query(ll,rr,l,m,rt<<1);
51     if (rr>m)
52     ret+=query(ll,rr,m+1,r,rt<<1|1);
53     return ret;
54 }
55 int main()
56 {
57     int t,casee=0;
58     char q[10];
59     //freopen("de.txt","r",stdin);
60     scanf("%d",&t);
61     while (t--)
62     {
63         printf("Case %d:
",++casee);
64         int n;
65         scanf("%d",&n);
66         build(1,n,1);
67         while (~scanf("%s",q))
68         {
69             if (q[0]=='E')
70             break;
71             int x,y;
72             scanf("%d%d",&x,&y);
73             if (q[0]=='Q')
74             {
75                 int ans=query(x,y,1,n,1);
76                 printf("%d
",ans);
77             }
78             if (q[0]=='S')
79             update(x,-y,1,n,1);
80             if (q[0]=='A')
81             update(x,y,1,n,1);
82         }
83     }
84     return 0;
85 }

就是这样了，现在说点题外话，那个博主也是大一开始打的ACM，感觉自己和他差距真的好大啊。现在要倍加努力！