uestc 1073 秋实大哥与线段树 Label：线段树

秋实大哥与线段树

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

“学习本无底，前进莫徬徨。” 秋实大哥对一旁玩手机的学弟说道。

秋实大哥是一个爱学习的人，今天他刚刚学习了线段树这个数据结构。

为了检验自己的掌握程度，秋实大哥给自己出了一个题，同时邀请大家一起来作。

秋实大哥的题目要求你维护一个序列，支持两种操作：一种是修改某一个元素的值；一种是询问一段区间的和。

Input

第一行包含一个整数

接下来一行包含

接下来一行包含一个整数

接下来

1 x v : 表示将第x个元素的值改为v
2 l r : 表示询问[l,r]这个区间的元素和

Output

对于每一个

Sample input and output

Sample Input	Sample Output
3 1 2 3 3 2 1 2 1 1 5 2 1 2	3 7

代码树状数组

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #define ll long long
 6 using namespace std;
 7 ll bit[500005],a[500005];
 8 ll n,m;
 9 
10 ll sum(ll i){//求元素1~i的和 
11     ll s=0;
12     while(i>0){
13         s+=bit[i];
14         i-=i&(-i);
15     }
16     return s;
17 }
18 
19 void add(ll i,ll x){//将元素i加上x 
20     while(i<=n){
21         bit[i]+=x;
22         i+=i&(-i);
23     }
24 }
25 
26 int main(){
27     
28     scanf("%lld",&n);
29     for(int i=1;i<=n;i++){
30         scanf("%d",&a[i]);
31         add(i,a[i]);
32     }
33     
34     scanf("%lld",&m);
35     for(int i=1;i<=m;i++){
36         ll x=0,b=0,c=0;
37         scanf("%lld%lld%lld",&x,&b,&c);
38         if(x==1){
39             ll temp=c-a[b];//处理修改后的数与原数的差 
40             a[b]=c; 
41             add(b,temp);
42         }
43         else if(x==2){
44             ll temp=sum(c)-sum(b-1);
45             printf("%lld
",temp);
46         }
47     }
48     return 0;
49 }

用的树状数组，注意变量名要起好，像Line41我就直接写成了

add(x,temp);

果断WA

还有Line40，没写，思考一下就知道，可能对一个值多次修改，然后Orz

代码 zkw线段树

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #define ll long long
 6 using namespace std;
 7 ll tr[10000005];//记得改long long 
 8 ll n,temp,M,m;
 9 
10 void query(ll s,ll t){
11     ll ans=0;
12     
13     for(s=s+M-1,t=t+M+1;s^t^1;s>>=1,t>>=1){
14         if(~s&1) ans+=tr[s^1];
15         if(t&1)  ans+=tr[t^1];
16     }
17     
18     printf("%lld
",ans);
19 }
20 
21 void change(ll x,ll y){
22     for(tr[x+=M]+=y,x>>=1;x>0;x>>=1){
23         tr[x]=tr[x<<1]+tr[x<<1|1];
24     }
25 }
26 
27 int main(){
28 //    freopen("01.in","r",stdin);
29     scanf("%lld",&n);
30     for(M=1;M<(n+2);M<<=1);//定义M大小 
31 
32     for(ll i=1;i<=n;i++){
33         scanf("%lld",&temp);
34         change(i,temp);
35     }
36     
37     scanf("%lld",&m);
38     
39     for(ll i=1;i<=m;i++){
40         ll oper,s,t;
41         scanf("%lld%lld%lld",&oper,&s,&t);
42         if(oper==2){
43             query(s,t);
44         }
45         else if(oper==1){
46             temp=t-tr[s+M];
47             change(s,temp);
48         }
49     }
50     return 0;
51 }

Line 22

x>>=1

一定要写

还有就是Line 30之前放到Line 36，诡异的错误