uva 12086 线段树or树状数组练习

题目链接 https://vjudge.net/problem/34215/origin

这个题就是线段树裸题，有两种操作，实现单点更新和区间和的查找即可，这里第一次学习使用树状数组完成。

二者相比，BIT无论从时间，空间还是代码量考虑都要优于ST，所以遇见这种求解区间和的操作考虑使用BIT。

 1 /*线段树 250 ms*/
 2 
 3 #include<bits/stdc++.h>
 4 using namespace std;
 5 #define M ((L+R)>>1)
 6 #define lc (id<<1)
 7 #define rc ((id<<1)|1)
 8 int sumv[(200000<<2)+10];
 9 void build(int L,int R,int id)
10 {
11     if(L==R){scanf("%d",&sumv[id]);return;}
12     build(L,M,lc);
13     build(M+1,R,rc);
14     sumv[id]=sumv[lc]+sumv[rc];
15 }
16 void update(int L,int R,int id,int x,int y)
17 {
18  if(L==R) {sumv[id]=y;return;}
19  if(x<=M)update(L,M,lc,x,y);
20  else update(M+1,R,rc,x,y);
21  sumv[id]=sumv[lc]+sumv[rc];
22 }
23 int ask(int L,int R,int id,int l,int r)
24 {
25     if(L>=l&&R<=r) {return sumv[id];}
26     if(r<=M) return ask(L,M,lc,l,r);
27     else if(l>M) return ask(M+1,R,rc,l,r);
28     else return ask(L,M,lc,l,r)+ask(M+1,R,rc,l,r);
29 }
30 int main()
31 {
32     int N,i,j,x,y,k=0;
33     char s[100];
34     while(cin>>N&&N){
35         build(1,N,1);
36         if(k>0) puts("");
37         printf("Case %d:
",++k);
38         while(scanf("%s",s)!=EOF){
39             if(!strcmp(s,"END")) break;
40             scanf("%d%d",&x,&y);
41             if(!strcmp(s,"M")) printf("%d
",ask(1,N,1,x,y));
42             else update(1,N,1,x,y);
43         }
44     }
45     return 0;
46 }
47 
48 /*树状数组 180ms  */
49 
50 #include<bits/stdc++.h>
51 using namespace std;
52 int sumv[200000+15],n;
53 int a[200000+15];
54 int lowbit(int x){return x&-x;}
55 int sum(int x)
56 {
57     int ret=0;
58     while(x>0){
59         ret+=sumv[x];
60         x-=lowbit(x);
61     }
62     return ret;
63 }
64 void add(int x,int d)
65 {
66     while(x<=n){
67         sumv[x]+=d;
68         x+=lowbit(x);
69     }
70 }
71 int main()
72 {
73     int k=0;
74     while(scanf("%d",&n)!=EOF&&n){memset(sumv,0,sizeof(sumv));
75         for(int i=1;i<=n;++i){
76             int x;
77             scanf("%d",&x);
78             a[i]=x;
79             add(i,x);
80         }
81         char s[112];
82         if(k>0) puts("");
83         printf("Case %d:
",++k);
84         while(scanf("%s",s)!=EOF){
85             if(!strcmp(s,"END")) break;
86             int x,y;
87             scanf("%d%d",&x,&y);
88             if(s[0]=='M'){
89                 printf("%d
",sum(y)-sum(x-1));
90             }
91             else{
92                 add(x,y-a[x]);
93                 a[x]=y;
94             }
95         }
96     }
97     return 0;
98 }