NENU_CS_segment

NENU_CS_segment_tree

单点更新

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

题意：单点更新加减，区间查询求和。

 1 #include<cstdio>
 2 #define lrrt int L,int R,int rt
 3 #define iall 1,n,1
 4 #define imid int mid=(L+R)>>1
 5 #define lson L,mid,rt<<1
 6 #define rson mid+1,R,rt<<1|1
 7 const int M=5e4+10;
 8 int a[M];
 9 char op[32];
10 int tree[M<<2];
11 void pushup(int rt){
12     tree[rt]=tree[rt<<1]+tree[rt<<1|1];
13 }
14 void build(lrrt){
15     if(L==R){
16         tree[rt]=a[L];
17         return ;
18     }
19     imid;
20     build(lson);
21     build(rson);
22     pushup(rt);
23 }
24 void update(int x,int y,lrrt){
25     if(L==R){
26         tree[rt]+=y;
27         return ;
28     }
29     imid;
30     if(mid>=x) update(x,y,lson);
31     else       update(x,y,rson);
32     pushup(rt);
33 }
34 int query(int x,int y,lrrt){
35     if(x<=L&&R<=y) return tree[rt];
36     imid;
37     int ans=0;
38     if(mid>=x) ans+=query(x,y,lson);
39     if(mid<y)  ans+=query(x,y,rson);
40     return ans;
41 }
42 int main(){
43     int t,n,x,y;
44     while(~scanf("%d",&t)){
45         int cas=1;
46         while(t--){
47             scanf("%d",&n);
48             for(int i=1;i<=n;i++){
49                 scanf("%d",&a[i]);
50             }
51             build(iall);
52             printf("Case %d:
",cas++);
53             while(true){
54                 scanf("%s",op);
55                 if(op[0]=='E') break;
56                 scanf("%d%d",&x,&y);
57                 if(op[0]=='Q'){
58                     printf("%d
",query(x,y,iall));
59                     continue;
60                 }
61                 if(op[0]=='S') y=-y;
62                 update(x,y,iall);
63             }
64         }
65     }
66     return 0;
67 }

View Code

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

题意：单点赋值，区间查询最大值。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define lrrt int L,int R,int rt
 4 #define iall 1,n,1
 5 #define imid int mid=(L+R)>>1
 6 #define lson L,mid,rt<<1
 7 #define rson mid+1,R,rt<<1|1
 8 using namespace std;
 9 const int M=2e5+10;
10 int a[M];
11 int tree[M<<2];
12 void pushup(int rt){
13     tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);
14 }
15 void build(lrrt){
16     if(L==R){
17         tree[rt]=a[L];
18         return ;
19     }
20     imid;
21     build(lson);
22     build(rson);
23     pushup(rt);
24 }
25 int query(int x,int y,lrrt){
26     if(x<=L&&R<=y) return tree[rt];
27     imid;
28     int ans=0;
29     if(mid>=x) ans=max(ans,query(x,y,lson));
30     if(mid<y)  ans=max(ans,query(x,y,rson));
31     return ans;
32 }
33 void update(int x,int y,lrrt){
34     if(L==R){
35         tree[rt]=y;
36         return ;
37     }
38     imid;
39     if(mid>=x) update(x,y,lson);
40     else       update(x,y,rson);
41     pushup(rt);
42 }
43 int main(){
44     int n,m,x,y;
45     char op[4];
46     while(~scanf("%d%d",&n,&m)){
47         for(int i=1;i<=n;i++){
48             scanf("%d",&a[i]);
49         }
50         build(iall);
51         while(m--){
52             scanf("%s%d%d",op,&x,&y);
53             if(op[0]=='Q'){
54                 printf("%d
",query(x,y,iall));
55                 continue;
56             }
57             update(x,y,iall);
58         }
59     }
60     return 0;
61 }

View Code

成段更新

end