秋實(shí)大哥與線段樹

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

“學(xué)習(xí)本無底，前進(jìn)莫徬徨。” 秋實(shí)大哥對(duì)一旁玩手機(jī)的學(xué)弟說道。

秋實(shí)大哥是一個(gè)愛學(xué)習(xí)的人，今天他剛剛學(xué)習(xí)了線段樹這個(gè)數(shù)據(jù)結(jié)構(gòu)。

為了檢驗(yàn)自己的掌握程度，秋實(shí)大哥給自己出了一個(gè)題，同時(shí)邀請(qǐng)大家一起來作。

秋實(shí)大哥的題目要求你維護(hù)一個(gè)序列，支持兩種操作：一種是修改某一個(gè)元素的值；一種是詢問一段區(qū)間的和。

Input

第一行包含一個(gè)整數(shù)nn，表示序列的長(zhǎng)度。

接下來一行包含nn個(gè)整數(shù)aiai，表示序列初始的元素。

接下來一行包含一個(gè)整數(shù)mm，表示操作數(shù)。

接下來mm行，每行是以下兩種操作之一：

1 x v : 表示將第x個(gè)元素的值改為v 2 l r : 表示詢問[l,r]這個(gè)區(qū)間的元素和

1≤n，m，v，ai≤1000001≤n，m，v，ai≤100000，1≤l≤r≤n1≤l≤r≤n。

Output

對(duì)于每一個(gè)22?ll?rr操作，輸出一個(gè)整數(shù)占一行，表示對(duì)應(yīng)的答案。

Sample input and output

Sample InputSample Output

3 1 2 3 3 2 1 2 1 1 5 2 1 2	3 7

代碼 ?樹狀數(shù)組

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];//處理修改后的數(shù)與原數(shù)的差 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\n",temp); 46 } 47 } 48 return 0; 49 }

用的樹狀數(shù)組，注意變量名要起好，像Line41我就直接寫成了

add(x,temp);

果斷WA

?

還有Line40，沒寫，思考一下就知道，可能對(duì)一個(gè)值多次修改，然后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\n",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，詭異的錯(cuò)誤

轉(zhuǎn)載于:https://www.cnblogs.com/radiumlrb/p/5823786.html

總結(jié)

以上是生活随笔為你收集整理的uestc 1073 秋实大哥与线段树 Label：线段树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。