0018：線段樹詳解
先來看一道模板題：
//www.luogu.com.cn/problem/P3372
題目描述：
已知一個數列，你需要進行下面兩種操作：
1.將某區間每一個數加上 k。
2.求出某區間每一個數的和。
一看是區間查詢和區間更新的題，就很容易想到線段樹——線段樹就是用來解決區間類型的題的。
那麼什麼是線段樹呢？假如我們把{1,5,4,2,3}存入線段樹，會是這樣：
（黑色是區間，藍色是區間所有數的和，紅色是下標）
根據這張圖，不難得出：
左兒子的下標=父節點下標*2； 右兒子的下標=父節點下標*2+1
那麼我們就可以以這個規律遞歸建樹了。
void P(long long id){//sum是區間所有數的和 t[id].sum=t[id*2].sum+t[id*2+1].sum; } void build(long long id,long long l,long long r){//建樹 t[id].l=l; t[id].r=r;//將左右端點賦值 if(l==r){ t[id].sum=arr[r]; }else{ long long mid=(l+r)/2;//二分遞歸建樹 build(id*2,l,mid); build(id*2+1,mid+1,r); P(id);//更新父節點sum值 } }
區間查詢也基本是同理。
區間更新有點不同，那就是需要懶標記來節省時間。
就是我們更新一個父節點之後，將它打上懶標記，等到下次遍歷到它的時候將他的懶標記下傳，並更新子節點。
上代碼：
1 #include<bits/stdc++.h> 2 using namespace std; 3 long long arr[100001]; 4 struct O{ 5 long long sum,lazy,l,r;//由於這道題數據是2^63，所以要用long long，否則只有70分 6 }t[400004]; 7 void P(long long id){//sum是區間所有數的和 8 t[id].sum=t[id*2].sum+t[id*2+1].sum; 9 } 10 void PD(long long id){//用lazy數組進行延遲操作 11 t[id*2].lazy+=t[id].lazy; 12 t[id*2+1].lazy+=t[id].lazy; 13 t[id*2].sum+=(t[id*2].r-t[id*2].l+1)*t[id].lazy; 14 t[id*2+1].sum+=(t[id*2+1].r-t[id*2+1].l+1)*t[id].lazy; 15 t[id].lazy=0; 16 } 17 void build(long long id,long long l,long long r){//建樹 18 t[id].l=l; 19 t[id].r=r;//將左右端點賦值 20 if(l==r){ 21 t[id].sum=arr[r]; 22 }else{ 23 long long mid=(l+r)/2;//二分遞歸建樹 24 build(id*2,l,mid); 25 build(id*2+1,mid+1,r); 26 P(id);//更新父節點sum值 27 } 28 } 29 long long Q(long long L,long long R,long long id){//區間查詢 30 if(t[id].l>R||t[id].r<L){//如果沒有重合部分，直接返回 31 return 0; 32 } 33 if(t[id].l>=L&&t[id].r<=R){//如果當前的左右端點正好在題目給的L、R裏面，返回當前節點的sum值 34 return t[id].sum; 35 } 36 if(t[id].lazy>0){//如果lazy大於0，證明當前節點之前被lazy標記了，更新子節點的sum、lazy值並將當前節點lazy值清零 37 PD(id); 38 } 39 return Q(L,R,id*2)+Q(L,R,id*2+1);//遞歸更新區間和 40 } 41 void W(long long L,long long R,long long id,long long x){ 42 if(t[id].l>R||t[id].r<L){ 43 return; 44 } 45 if(L<=t[id].l&&R>=t[id].r){ 46 t[id].sum+=(t[id].r-t[id].l+1)*x;//這裡由於是求和，所以是區間長度*要加上的數 47 t[id].lazy+=x;//lazy數組加上x 48 return; 49 } 50 if(t[id].lazy>0){ 51 PD(id); 52 } 53 W(L,R,id*2,x); 54 W(L,R,id*2+1,x); 55 P(id);//更新父節點sum值 56 } 57 int main(){ 58 int n,m,a,b,c,d; 59 cin>>n>>m; 60 for(int i=1;i<=n;i++){ 61 cin>>arr[i]; 62 } 63 build(1,1,n); 64 while(m--){ 65 cin>>a; 66 if(a==2){ 67 cin>>b>>c; 68 cout<<Q(b,c,1)<<endl; 69 }else{ 70 cin>>b>>c>>d; 71 W(b,c,1,d); 72 } 73 } 74 }
