數據結構-線段樹
- 2020 年 3 月 8 日
- 筆記
數據結構-線段樹
參考資料
暫無
線段樹是所有 RMQ 中最常用的數據結構。
功能：區間修改區間查詢。不止最值、求和。只要可遞推的值都可以構造線段樹。
如果區間大小為 (n)，線段樹有 (cnt) 個節點，那麼 (2n-1le cnt<4n)。
節點
對於每個節點 (x)，和堆類似，父親節點為 (x>>1)（即 (x/2) 下取整的位運算方法，位運算方便而且快），左兒子為 (x<<1)（即 (2x)），右兒子為 (x<<1|1)（即 (2x+1)）。
同時每個節點對應一段區間，所以叫線段樹。節點 (1) 對應的區間為 (1sim n)。設一個節點對應的區間為 (lsim r)，那麼它的左兒子對應的區間就是 (lsim mid)，其中 (mid=(l+r)>>1)，右兒子區間為 (mid+1sim r)。如果一個節點對應單點區間，就沒有兒子。
同時每個節點對應一個值，即該區間的 RMQ 值。如果是求最值問題，就表示該區間最大值；如果是求和問題，就表示該區間的和。
操作（單點修改區間查詢）
一個線段樹是求和還是求最值或者求別的東西，取決於 (pushup(k)) 函數，其中 (k) 為節點編號，時間複雜度 (O(1))。
void pushup(int k){v[k]=max(v[k<<1],v[k<<1|1]);}//求最大值根據原序列構造初始的線段樹用 (build()) 函數，單點節點上的值就為單點的值，遞歸從下到上構造，時間複雜度 (O(nlog n))。
void build(int k=1,int l=1,int r=n){//表示外部應用默認k=1,l=1,r=n if(l==r){v[k]=a[l];return;} //單點節點 build(k<<1,l,mid),build(k<<1|1,mid+1,r); //遞歸構造 pushup(k); //遞推 }先講單點修改（加上 (y)），只需與 (build()) 函數類似的遞歸操作即可，如果到達單點節點，就修改，不走那些跟查詢單點沒關係的區間、別忘了修改完後也要遞推，時間複雜度 (O(log n))。
void fix(int x,int y,int k=1,int l=1,int r=n){ if(l==x&&r==x){v[k]+=y;return;} //單點修改 if(mid>=x) fix(x,y,k<<1,l,mid); //遞歸左兒子 else fix(x,y,k<<1|1,mid+1,r); //遞歸右兒子 pushup(k);//遞推 }區間查詢，如果單前節點在查詢區間內，就返回值。否則，遞歸左兒子右兒子，遞推得區間查詢值。時間複雜度 (O(log n))，因為只會走相關的 (log n) 個節點。
int fmax(int x,int y,int k=1,int l=1,int r=n){ if(x<=l&&r<=y) return v[k]; //在查找區間內，返回值 int res=0; if(mid>=x) res=max(res,fmax(x,y,k<<1,l,mid)); if(mid<y) res=max(res,fmax(x,y,k<<1|1,mid+1,r)); return res; }總時間複雜度 (O(nlog n)) ，全程式碼：
#include <bits/stdc++.h> using namespace std; const int N=1e5+10; int n,m,a[N]; namespace Sumtree{ #define mid ((l+r)>>1) int v[N<<2]; void pushup(int k){v[k]=max(v[k<<1],v[k<<1|1]);} void build(int k=1,int l=1,int r=n){ if(l==r){v[k]=a[l];return;} build(k<<1,l,mid),build(k<<1|1,mid+1,r); pushup(k); } void fix(int x,int y,int k=1,int l=1,int r=n){ if(l==x&&r==x){v[k]+=y;return;} if(mid>=x) fix(x,y,k<<1,l,mid); else fix(x,y,k<<1|1,mid+1,r); pushup(k); } int fmax(int x,int y,int k=1,int l=1,int r=n){ if(x<=l&&r<=y) return v[k]; int res=0; if(mid>=x) res=max(res,fmax(x,y,k<<1,l,mid)); if(mid<y) res=max(res,fmax(x,y,k<<1|1,mid+1,r)); return res; } #undef mid }using namespace Sumtree; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",a+i); build(); for(int i=1,x,y,z;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); if(x==1) fix(y,z); else printf("%dn",fmax(y,z)); } return 0; }線段樹如果只能單點修改區間查詢，程式碼還這麼長，就沒人用他了。所以可想而知，線段樹還可以區間修改，區間查詢。
操作（區間修改區間查詢）
先看如何區間修改，初學者會這麼寫：
void fix(int x,int y,int z,int k=1,int l=1,int r=n){ if(x<=l&&r<=y){v[k]+=z;return;} if(mid>=x) fix(x,y,z,k<<1,l,mid); if(mid<y) fix(x,y,z,k<<1|1,mid+1,r); pushup(k); }問題是這樣的話對於每個區間屬於 ([x,y]) 的節點，它的子節點就會沒被修改。
初學者還可能這麼寫：
void fix(int x,int y,int z,int k=1,int l=1,int r=n){ if(l==r){v[k]+=z;return;} if(mid>=x) fix(x,y,z,k<<1,l,mid); if(mid<y) fix(x,y,z,k<<1|1,mid+1,r); pushup(k); }問題在於時間複雜度為 (O(n))。
那麼區間修改的主角就要出場了——懶標記（(texttt{lazytag})）。對於每個節點，多加一個值，(mk[])。(mk[x]) 表示 (x) 節點的標記。每次修改在前面那個初學者的程式碼上加上終止區間懶標記。
void fix(int x,int y,int z,int k=1,int l=1,int r=n){ if(x<=l&&r<=y){v[k]+=z,mk[k]+=z;return;} pushdown(k); if(mid>=x) fix(x,y,z,k<<1,l,mid); if(mid<y) fix(x,y,z,k<<1|1,mid+1,r); pushup(k); }這時你注意到了上方程式碼第 (3) 行有一個 (pushdown(k))，那就是一個專門用來處理懶標記的函數，負責把標記下放，時間複雜度為 (O(1))。
void pushdown(int k){ if(!mk[k]) return; v[k<<1]+=mk[k],v[k<<1|1]+=mk[k]; mk[k<<1]+=mk[k],mk[k<<1|1]+=mk[k],mk[k]=0; }有了它，區間修改就沒必要一直修改到單點了，可以修改到所屬區間，然後記下懶標記。下次到這個區間的時候把它 (pushdown) 下放。
然後區間修改區間查詢的程式碼就是這樣：
#include <bits/stdc++.h> using namespace std; const int N=1e5+10; int n,m,a[N]; namespace Sumtree{ #define mid ((l+r)>>1) int v[N<<2],mk[N<<2]; void pushup(int k){v[k]=max(v[k<<1],v[k<<1|1]);} void pushdown(int k){ if(!mk[k]) return; v[k<<1]+=mk[k],v[k<<1|1]+=mk[k]; mk[k<<1]+=mk[k],mk[k<<1|1]+=mk[k],mk[k]=0; } void build(int k=1,int l=1,int r=n){ mk[k]=0; if(l==r){v[k]=a[l];return;} build(k<<1,l,mid),build(k<<1|1,mid+1,r); pushup(k); } void fix(int x,int y,int z,int k=1,int l=1,int r=n){ if(x<=l&&r<=y){v[k]+=z,mk[k]+=z;return;} pushdown(k); if(mid>=x) fix(x,y,z,k<<1,l,mid); if(mid<y) fix(x,y,z,k<<1|1,mid+1,r); pushup(k); } int fmax(int x,int y,int k=1,int l=1,int r=n){ if(x<=l&&r<=y) return v[k]; pushdown(k); int res=0; if(mid>=x) res=max(res,fmax(x,y,k<<1,l,mid)); if(mid<y) res=max(res,fmax(x,y,k<<1|1,mid+1,r)); return res; } #undef mid }using namespace Sumtree; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",a+i); build(); for(int i=1,x,y,z;i<=m;i++){ scanf("%d",&x); if(x==1) scanf("%d%d%d",&x,&y,&z),fix(x,y,z); else scanf("%d%d",&x,&y),printf("%dn",fmax(x,y)); } return 0; }時間複雜度還是 (O(nlog n)) 的。
線段樹有個經典例題，可以幫助你弄懂線段樹的其他操作。
[USACO08FEB]酒店Hotel
第一行輸入 (n)，(m)。(n) 代表有 (n) 個房間，編號為 (1sim n)，開始都為空房。(m) 表示以下有 (m) 行操作，以下每行先輸入一個數 (i)，表示一種操作：
若 (i) 為1，表示查詢房間。再輸入一個數 (x)，表示在 (1sim n) 房間中找到長度為 (x) 的連續空房，輸出連續 (x) 個房間中左端的房間號，盡量讓這個房間號最小。若找不到長度為 (x) 的連續空房，輸出(0)。並且在這 (x) 個空房間中住上人。
若 (i) 為 (2)，表示退房，再輸入兩個數 (x)，(y) 代表 房間號 (xsim x+y-1) 退房，即讓房間為空。
講解：
那麼這題中每個線段樹節點需要有四個值：
(texttt{lf[k]：})(k) 這個節點區間從左邊開始連續空房數。
(texttt{rt[k]：})(k) 這個節點區間從右邊開始連續空房數。
(texttt{v[k]：})(k) 這個節點區間內最長的連續空房數。
(texttt{mk[k]：})(k) 這個節點退房、住人區間修改懶標記。
所以有遞推式（其中 (?) 為三目運算符）：
void pushup(int k,int l,int r){ int mid=(l+r)>>1; lf[k]=lf[k<<1]==mid-l+1?lf[k<<1]+lf[k<<1|1]:lf[k<<1]; rt[k]=rt[k<<1|1]==r-mid?rt[k<<1|1]+rt[k<<1]:rt[k<<1|1]; v[k]=max(max(v[k<<1],v[k<<1|1]),rt[k<<1]+lf[k<<1|1]); }可以這麼初始化：
void build(int k=1,int l=1,int r=n){ mk[k]=-1; if(l==r){lf[k]=rt[k]=v[k]=1;return;} int mid=(l+r)>>1; build(k<<1,l,mid),build(k<<1|1,mid+1,r); pushup(k,l,r); }重點在於怎麼查詢。如下程式碼，(find(x,k,l,r)) 表示尋找 (k) 這個節點區間里尋找最左的連續 (x) 空房。
int find(int x,int k=1,int l=1,int r=n){ if(v[k]<x) return -1; //如果區間內最長連續空房小於x，逃 int mid=(l+r)>>1; pushdown(k,l,r);//千萬別忘了pushdown if(v[k<<1]>=x) return find(x,k<<1,l,mid); //如果左兒子有滿足要求的區間，返回左兒子滿足要求的區間左端點 if(rt[k<<1]+lf[k<<1|1]>=x) return mid-rt[k<<1]+1;//如果滿足區間橫跨左右兒子區間，返回橫跨區間左端點 return find(x,k<<1|1,mid+1,r);//返回右兒子滿足區間左端點 }可以發現，這個程式碼的時間複雜度也是 (O(nlog n)) 的。
蒟蒻的 (color{#44cc00}texttt{AC}) 程式碼：
#include <bits/stdc++.h> using namespace std; const int N=5e4+10; int n,m; namespace sumtree{ int lf[N<<2],rt[N<<2],v[N<<2],mk[N<<2]; void pushup(int k,int l,int r){ int mid=(l+r)>>1; lf[k]=lf[k<<1]==mid-l+1?lf[k<<1]+lf[k<<1|1]:lf[k<<1]; rt[k]=rt[k<<1|1]==r-mid?rt[k<<1|1]+rt[k<<1]:rt[k<<1|1]; v[k]=max(max(v[k<<1],v[k<<1|1]),rt[k<<1]+lf[k<<1|1]); } void pushdown(int k,int l,int r){ if(mk[k]==-1) return; int mid=(l+r)>>1; lf[k<<1]=rt[k<<1]=v[k<<1]=(!mk[k])*(mid-l+1); lf[k<<1|1]=rt[k<<1|1]=v[k<<1|1]=(!mk[k])*(r-mid); mk[k<<1]=mk[k<<1|1]=mk[k],mk[k]=-1; } void build(int k=1,int l=1,int r=n){ mk[k]=-1; if(l==r){lf[k]=rt[k]=v[k]=1;return;} int mid=(l+r)>>1; build(k<<1,l,mid),build(k<<1|1,mid+1,r); pushup(k,l,r); } int find(int x,int k=1,int l=1,int r=n){ if(v[k]<x) return -1; if(l==r) return l; int mid=(l+r)>>1; pushdown(k,l,r); if(v[k<<1]>=x) return find(x,k<<1,l,mid); if(rt[k<<1]+lf[k<<1|1]>=x) return mid-rt[k<<1]+1; return find(x,k<<1|1,mid+1,r); } void clear(int x,int y,int k=1,int l=1,int r=n){ if(x<=l&&r<=y){ lf[k]=rt[k]=v[k]=r-l+1; mk[k]=0; return; } pushdown(k,l,r); int mid=(l+r)>>1; if(mid>=x) clear(x,y,k<<1,l,mid); if(mid<y) clear(x,y,k<<1|1,mid+1,r); pushup(k,l,r); } void full(int x,int y,int k=1,int l=1,int r=n){ if(x<=l&&r<=y){ lf[k]=rt[k]=v[k]=0; mk[k]=1; return; } pushdown(k,l,r); int mid=(l+r)>>1; if(mid>=x) full(x,y,k<<1,l,mid); if(mid<y) full(x,y,k<<1|1,mid+1,r); pushup(k,l,r); } }using namespace sumtree; int main(){ scanf("%d%d",&n,&m); build(); for(int i=1;i<=m;i++){ int op,x,y; scanf("%d",&op); if(op==1){ scanf("%d",&y); if((x=find(y))==-1) puts("0"); else { printf("%dn",x); full(x,x+y-1); } } else { scanf("%d%d",&x,&y); clear(x,x+y-1); } } return 0; }關於線段樹有很多後續知識，如線段樹合併，線段樹分裂，可持久化線段樹（主席樹）等，學習千萬不能停止腳步。
同時，線段樹的題目千變萬化，建議多練練線段樹的題。
祝大家學習愉快！
