hdu1166 敌兵布阵

hdu1166 敌兵布阵
题意:O(-1)
思路:O(-1)
线段树功能:update:单点增减 query:区间求和

这是一道最基本的线段树的题。

只需要建树，然后对树的节点更新。

然后是询问区间的和。

View Code

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