hdu 1166 敌兵布阵【线段树】

好好学一下线段树----
从0开始----加油～
单点更新的
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<vector>
 7 using namespace std;
 8 #define lp (p << 1)
 9 #define rp (p << 1 | 1)
10 #define getmid(l,r) (l + (r - l) / 2)
11 
12 const int maxn = 50005;
13 struct node{
14     int l,r,s;
15 }t[4*maxn];
16 
17 int a[maxn],n;
18 
19 int calc(int a,int b) { return a+b; }
20 
21 void Push_up(int p){
22     t[p].s = calc(t[lp].s,t[rp].s);
23 }
24 
25 void Build_tree(int p,int l,int r){
26     t[p].l = l;
27     t[p].r = r;
28     if(l == r){ t[p].s = a[l];return;}
29     int mid = getmid(l,r);
30     Build_tree(lp,l,mid);
31     Build_tree(rp,mid+1,r);
32     Push_up(p);
33 }
34 
35 void update(int p,int s,int w){//给s点加上w 
36     if(t[p].l == t[p].r) {
37         t[p].s += w;
38         return;
39     }
40     int mid = getmid(t[p].l,t[p].r);
41     if(s <= mid) update(lp,s,w);
42     else update(rp,s,w);
43     Push_up(p);        
44 }
45 
46 int sum(int p,int l,int r){
47     if(t[p].l == l && t[p].r == r) return t[p].s;
48     
49         int mid = getmid(t[p].l,t[p].r);
50         if(r <= mid) return sum(lp,l,r);
51         else if(mid < l) return sum(rp,l,r);
52          else return calc(sum(lp,l,mid),sum(rp,mid+1,r));
53 }
54 
55 int main(){
56     int T;
57     scanf("%d",&T);
58     int kase = 0;
59     while(T--){
60         scanf("%d",&n);
61         for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
62         Build_tree(1,1,n);
63         
64     //    for(int i = 1;i <= n;i++)
65     //    printf("t[%d].l = %d  t[%d].r = %d  t[%d].s = %d
",i,t[i].l,i,t[i].r,i,t[i].s);
66         
67         char cmd[10];
68         int x,y;
69         printf("Case %d:
",++kase);
70         while(cin >> cmd){
71             if(cmd[0] == 'E') break;
72             else if(cmd[0] == 'A'){
73             scanf("%d %d",&x,&y);
74             update(1,x,y);
75             }
76             else if(cmd[0] == 'S'){
77             scanf("%d %d",&x,&y);
78             update(1,x,-y);
79             }
80             else{
81                 scanf("%d %d",&x,&y);
82                 printf("%d
",sum(1,x,y));
83             }
84         }    
85     }
86     return 0;
87 }
View Code
hdu 1166 敌兵布阵 【线段树】

hdu 1166 敌兵布阵【线段树】
