线段树 HDU 1166 【学习代码】

代码出处：http://www.notonlysuccess.com/index.php/segment-tree-complete/

这个是基础线段树，用树形数组实现的。

实现，查询，建树，添加修改结点信息。

 1 #include <stdio.h>
 2 #define lson l,m,rt<<1
 3 #define rson m+1,r,rt<<1|1
 4 #define maxn 55555
 5 int sum[maxn<<2];
 6 void PushUp(int rt)
 7 {
 8     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
 9 }
10 void build(int l,int r,int rt)
11 {
12     if(l==r)
13     {
14         scanf("%d",&sum[rt]);
15         return;
16     }
17     int m=(l+r)>>1;
18     build(lson); build(rson);
19     PushUp(rt);
20 }
21 void update(int p,int add,int l,int r,int rt)
22 {
23     if(l==r)
24     {
25         sum[rt]+=add;
26         return;
27     }
28     int m=(l+r)>>1;
29     if(p<=m) update(p,add,lson);
30     else     update(p,add,rson);
31     PushUp(rt);
32 }
33 int query(int L,int R,int l,int r,int rt)
34 {
35     if(L<=l&&r<=R)
36     {
37         return sum[rt];
38     }
39     int m=(l+r)>>1;
40     int res=0;
41     if(L<=m) res+=query(L,R,lson);
42     if(R>m)     res+=query(L,R,rson);
43     return res;
44 }
45 int main()
46 {
47     int T,n;
48     int a,b;
49     char op[10];
50     scanf("%d",&T);
51     for(int cas=1;cas<=T;cas++)
52     {
53         printf("Case %d:\n",cas);
54         scanf("%d",&n);
55         build(1,n,1);
56         while(scanf("%s",op))
57         {
58             if(op[0]=='E') break;
59             scanf("%d%d",&a,&b);
60             if(op[0]=='Q')
61                 printf("%d\n",query(a,b,1,n,1));
62             else if(op[0]=='S') update(a,-b,1,n,1);
63             else                update(a,b,1,n,1);
64         }
65     }
66     return 0;
67 }