?

codevs 1082 線段樹練習3

鏈接：http://codevs.cn/problem/1082/

?

sumv是維護求和的線段樹，addv是標記這歌節點所在區間還需要加上的值。

我的線段樹寫法在運用的時候，需要更新或查找的區間是儲存在y1,y2變量里面的，值是儲存在變量v里面的，查詢結果儲存在變量_sum里面。

每次更新（調用update函數）時，必須要維護更新區間上層的線段樹，即更新節點上面的線段樹表示的和是準確的和。

在update函數更新的時候，如果線段樹分成區間包含于所要求的區間那么直接在addv上記錄下要加的值，否則再次細分區間。最后要再維護一下（調用pushdown函數），這樣就保證了線段樹的和性質。

?

pushdown函數非常重要，在我的寫法里，它有兩個作用，一個是標記下放，另一個是結算和維護。注意在結算和的時候，要把左右兒子的addv和的也要加上去，否則會漏值。查詢的時候也要用到pushdown，否則addv的值會在細分區間的時候漏掉，但查詢（query函數）的pushdown不太樣，要加入一個判斷：只有當addv值不為0的時候才標記下放。如果不這樣，本來一個對的值就會被重新計算，從而破壞了線段樹的性質。

?

附上代碼：

1 #include<cstdio> 2 #include<iostream> 3 #define LL long long int 4 using namespace std; 5 const int maxn=300010; 6 7 LL n,k,A[maxn],sumv[maxn*4],addv[maxn*4]; 8 9 void init(int o,int L,int R)//初始化建樹 10 { 11 if(L==R) sumv[o]=A[L]; 12 else 13 { 14 int M=(L+R)/2; 15 init(o*2,L,M); 16 init(o*2+1,M+1,R); 17 sumv[o]=sumv[o*2]+sumv[o*2+1]; 18 } 19 } 20 21 void pushdown(int o,int L,int R)//標記下放 22 { 23 int M=(L+R)/2; 24 if(L!=R) sumv[o]=sumv[o*2]+sumv[o*2+1]+addv[o]*(R-L+1)+addv[o*2]*(M-L+1)+addv[o*2+1]*(R-M); 25 else sumv[o]+=addv[o]; 26 addv[o*2]+=addv[o]; 27 addv[o*2+1]+=addv[o]; 28 addv[o]=0; 29 } 30 31 int y1,y2,v; 32 void update(int o,int L,int R)//更新 33 { 34 if(y1<=L && R<=y2) addv[o]+=v; 35 else 36 { 37 int M=(L+R)/2; 38 if(y1<=M) update(o*2,L,M); 39 if(y2>M) update(o*2+1,M+1,R); 40 } 41 pushdown(o,L,R); 42 } 43 44 LL _sum,p; 45 void query(int o,int L,int R)//查詢 46 { 47 if(addv[o]!=0) pushdown(o,L,R); 48 if(y1<=L && R<=y2) _sum+=sumv[o]; 49 else 50 { 51 int M=(L+R)/2; 52 if(y1<=M) query(o*2,L,M); 53 if(y2>M) query(o*2+1,M+1,R); 54 } 55 } 56 57 int main() 58 { 59 cin>>n; 60 for(int i=1;i<=n;i++) cin>>A[i]; 61 init(1,1,n); 62 cin>>k; 63 for(int i=1,tp,x,y,z;i<=k;i++) 64 { 65 cin>>tp; 66 if(tp==1) 67 { 68 cin>>x>>y>>z; 69 y1=x,y2=y,v=z; 70 update(1,1,n); 71 } 72 else 73 { 74 cin>>x>>y; 75 y1=x,y2=y,_sum=0; 76 query(1,1,n); 77 cout<<_sum<<endl; 78 } 79 } 80 return 0; 81 }

?

轉載于:https://www.cnblogs.com/frankscode/p/6239091.html

總結

以上是生活随笔為你收集整理的codevs 1082 线段树区间求和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。