樹鏈剖分 講解+模板+習題

今天我們來講一下樹鏈剖分

樹鏈剖分是什么？

樹鏈剖分是一種用來維護樹上路徑信息的在線方法，可以處理在線。

通常通過一種方法，將一棵樹剖分成若干條鏈，然后通過數據結構（線段樹，BIT等）去維護。

我們通常所說的樹鏈剖分，基本都是輕重鏈剖分。

下面我們介紹一下這一種剖分。

學習樹鏈剖分的基礎知識有lca，dfs序，線段樹等。

首先，我們來明確即可變量。

\(size_i\)表示以\(i\)為子樹的大小，包括\(i\)

\(heavy_i\)表示\(i\)的所有兒子\(j\)中\(size_j\)最大的一個

連接\(i\)和\(heavy_i\)的邊稱為重邊(\(heavy\) \(edges\))，其余為輕邊(\(light\) \(edges\))

當好多條重邊首尾相連，形成了一條更大的重邊時，我們稱這個重邊的集合叫重鏈（\(heavy\) \(path\)）

因為不可能有兩條重鏈相交（根據重鏈定義可知），所以整棵樹被劃分成了若干條互不相交的重鏈。

舉個例子

紅色的邊是重邊，黑色是輕邊。1-2-4-8-16構成了一條重鏈。

其中所有的重鏈都不相交

再給一些剖分的性質。

1. 每個點只屬于一個重鏈。
2. 不可能有兩條重鏈相鄰。
3. 從一個點開始，重復"重鏈頂端-->跳一條輕邊"這個過程，必定能到根
4. 按上述方法跳，必定能在\(O(logn)\)步到達頂點。

給一下第4條的證明。

如果一條邊是重鏈，那他一次肯定能跳到重鏈頂端，這樣很快，

而沒經過一條輕邊，根據重鏈的定義，輕邊所在子樹\(size\)< \(\frac{1}{2}\) 所有子樹\(size\) ，則沒經過一條輕邊，該點得子樹大小必定\(*2\)甚至更多，則只會有\(O(logn)\)次。

那我們怎么通過代碼處理輕重邊剖分？

一種經典的處理方法如下。

設
\(father_x\)表示\(x\)的父親節點
\(size_x\)表示\(x\)的子樹大小
\(deep_x\)表示\(x\)的深度
\(heavy_x\)表示\(x\)的重兒子
\(top_x\) 表示\(x\)的重鏈頂點

處理以上幾個數組通常使用兩遍dfs處理。

第一次構建前4個數組

第二次本質是對重鏈進行標號與整理

每次遍歷到某點時，先遞歸它的重兒子，

在遞歸他的輕兒子，它的重鏈頂端就是自己

順便處理\(top_x\)

兩遍dfs代碼：

void dfs1(int rt){size[rt]=1;for (int i=0;i<e[rt].size();i++){int to=e[rt][i] ;if (to==fa[rt]) continue ; fa[to]=rt;dep[to]=dep[rt]+1 ;//信息 dfs1(to) ;size[rt]+=size[to] ;if (!hson[rt] || size[to]>size[hson[rt]]) hson[rt]=to ;//處理重兒子 }
} 
void dfs2(int rt,int t){top[rt]=t ;if (!hson[rt]) return ;dfs2(hson[rt],t) ;//先遞歸重兒子 for (int i=0;i<e[rt].size();i++){int to=e[rt][i] ;if (to==fa[rt] || to==hson[rt]) continue ;dfs2(to,to) ;//輕邊頂端為自己 }
}

之后，我們用線段樹維護每條重鏈的信息（在實際操作中，輕邊也算作重鏈）

在此同時，我們需要記錄每個節點的時間戳\(dfn_x\)，同樣最好記錄每個\(dfn_x\)對應的節點，我們用\(seq_x\)表示。

這兩個操作也非常簡單，只需在dfs2初始時加這兩句話：

    dfn[rt]=++tot ;seq[tot]=rt ;

因為我們是先處理重兒子的，所以重鏈的節點肯定會被放在線段樹的同一個區間中，這樣方便線段樹操作。

之后上面的剖分過程大體就結束了。

樹鏈剖分能夠暴力求出兩兩點的\(lca\)

為何說暴力，因為它不像倍增一樣要枚舉\(2^j\)步，他就是每次跳，而且時間復雜度有保障!

我們來講一講這個過程。

先上一張圖

如果要查詢9和11的lca，我們手動模擬一下：

1.首先11的dep較大，11跳至1（\(fa[top[11]]\)）
因為\(top[9]=top[11]，\)所以結束循環，判定深度小的位\(lca\)即可

void lca(int x,int y){int fx=top[x],fy=top[y] ;while(fx!=fy){if (dep[x]<dep[y]){ //跳x swap(x,y) ;swap(fx,fy) ;}x=fa[fx];fx=top[x] ;}if (dep[x]>dep[y]) swap(x,y) ;return y ;
} 

了解了樹剖解救lca的過程，基本你已經掌握了樹剖了，只差來幾道例題，我們不妨講解幾道例題，更深入了解樹剖一下。

我們拿BZOJ 1036 樹的統計 舉個例子。

它讓你動態干三件事：

1. 把某個點的權值改成t
2. 詢問x到y的路徑上的節點權值的最大值
3. 詢問x到y的路徑上的所以節點權值的和

這是一個樹鏈剖分的裸題。

他讓我們動態維護兩兩點的路徑信息。

假設我們剖分寫好了，線段樹也建好了，我們該怎么求出x到y的路徑上的節點權值的最大值和總和呢？

舉個例子。

同樣是9和11的例子。

11跳到1，我們已經維護2~11的最大值和和，為3和6

之后維護1到9的最大值和和，為5和10

MAX=5 SUM=16

int linkmax(int x,int y){ //鏈上最大值int fx=top[x],fy=top[y],ans=-inf ;while(fx!=fy){if (dep[fx]<dep[fy]){swap(x,y) ;swap(fx,fy) ;} ans=max(ans,qmax(1,dfn[fx],dfn[x])) ;x=fa[fx] ;fx=top[x] ;}if (dep[x]>dep[y]) swap(x,y) ;//在同一條重鏈上 ans=max(ans,qmax(1,dfn[x],dfn[y])) ;return ans ;
}
int linksum(int x,int y){ //鏈上和int fx=top[x],fy=top[y],ans=0 ;while(fx!=fy){if (dep[fx]<dep[fy]){swap(x,y) ;swap(fx,fy) ;}ans+=qsum(1,dfn[fx],dfn[x]) ;x=fa[fx] ;fx=top[x] ;}if (dep[x]>dep[y]) swap(x,y) ;ans+=qsum(1,dfn[x],dfn[y]) ;return ans ;
}

建議自己手動模擬一下，對于理解算法有很大作用

代碼：

#include <bits/stdc++.h>
using namespace std ;
const int N = 30010 ;
const int inf = (1<<30) ;
#define rep(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define REP(i,a,b) for (int (i)=(a);(i)>=(b);(i)--)
#define ls ((rt)<<1)
#define rs ((rt)<<1|1)
typedef long long ll ;vector <int> e[N] ;
int a[N],size[N],fa[N],dep[N],hson[N],top[N],dfn[N],seq[N] ;
int n,Q,tot,x,y,u,t ;
char op[20] ;struct node{int l,r,Max,sum;}tr[N<<2];void dfs1(int rt){size[rt]=1;for (int i=0;i<e[rt].size();i++){int to=e[rt][i] ;if (to==fa[rt]) continue ; fa[to]=rt;dep[to]=dep[rt]+1 ;dfs1(to) ;size[rt]+=size[to] ;if (!hson[rt] || size[to]>size[hson[rt]]) hson[rt]=to ;}
} 
void dfs2(int rt,int t){top[rt]=t ;dfn[rt]=++tot ;seq[tot]=rt ;if (!hson[rt]) return ;dfs2(hson[rt],t) ;for (int i=0;i<e[rt].size();i++){int to=e[rt][i] ;if (to==fa[rt] || to==hson[rt]) continue ;dfs2(to,to) ;}
}
inline void pushup(int rt){tr[rt].Max=max(tr[ls].Max,tr[rs].Max) ;tr[rt].sum=tr[ls].sum+tr[rs].sum ;
} 
void build(int rt,int l,int r){tr[rt].l=l;tr[rt].r=r ;if (l==r){tr[rt].Max=tr[rt].sum=a[seq[l]] ;return ; }int mid=(l+r)>>1;build(ls,l,mid) ;build(rs,mid+1,r) ;pushup(rt) ;
}
void modify(int rt,int pos){if (tr[rt].l==tr[rt].r){tr[rt].Max=tr[rt].sum=a[seq[tr[rt].l]] ;return ;}int mid=(tr[rt].l+tr[rt].r)>>1 ;if (pos<=mid) modify(ls,pos) ;else modify(rs,pos) ;pushup(rt) ;
}
int qmax(int rt,int l,int r){if (l<=tr[rt].l && tr[rt].r<=r) return tr[rt].Max ;int mid=(tr[rt].l+tr[rt].r)>>1 ;if (r<=mid) return qmax(ls,l,r) ;if (l>mid) return qmax(rs,l,r) ;return max(qmax(ls,l,r),qmax(rs,l,r)) ;
} 
int qsum(int rt,int l,int r){if (l<=tr[rt].l && tr[rt].r<=r) return tr[rt].sum ;int mid=(tr[rt].l+tr[rt].r)>>1 ;if (r<=mid) return qsum(ls,l,r) ;if (l>mid) return qsum(rs,l,r) ;return qsum(ls,l,r)+qsum(rs,l,r) ;
}
int linkmax(int x,int y){int fx=top[x],fy=top[y],ans=-inf ;while(fx!=fy){if (dep[fx]<dep[fy]){swap(x,y) ;swap(fx,fy) ;} ans=max(ans,qmax(1,dfn[fx],dfn[x])) ;x=fa[fx] ;fx=top[x] ;}if (dep[x]>dep[y]) swap(x,y) ;//在同一條重鏈上 ans=max(ans,qmax(1,dfn[x],dfn[y])) ;return ans ;
}
int linksum(int x,int y){int fx=top[x],fy=top[y],ans=0 ;while(fx!=fy){if (dep[fx]<dep[fy]){swap(x,y) ;swap(fx,fy) ;}ans+=qsum(1,dfn[fx],dfn[x]) ;x=fa[fx] ;fx=top[x] ;}if (dep[x]>dep[y]) swap(x,y) ;ans+=qsum(1,dfn[x],dfn[y]) ;return ans ;
}
int main(){scanf("%d",&n) ;for (int i=1;i<n;i++){scanf("%d%d",&x,&y) ;e[x].push_back(y) ; e[y].push_back(x) ;}for (int i=1;i<=n;i++) scanf("%d",&a[i]) ;fa[1]=0;dep[1]=1; dfs1(1) ;dfs2(1,1) ;build(1,1,n) ;scanf("%d",&Q) ;while(Q--){scanf("%s%d%d",op,&u,&t) ;if (op[0]=='C') a[u]=t,modify(1,dfn[u]) ;else if (op[1]=='M') printf("%d\n",linkmax(u,t)) ;else if (op[1]=='S') printf("%d\n",linksum(u,t)) ;}
}

一道雙倍經驗題：【模板】樹鏈剖分

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
const int N = 100010 ;
#define int long long
struct edge{int to,next ;
}e[N<<1];
int head[N],f[N],dep[N],size[N],son[N],rk[N],top[N],dfn[N];
int a[N];
//f[i]:i的父親,dep[i]:i的深度,size[i]:i的子樹大小,son[i]:重兒子 ,rk[i]:i的dfs值，與dfn相反
//top[i]:i所在鏈的頂端,dfn[i]:dfs序，時間戳 
int n,m,rt,tot,cnt;
int p,r ;
inline void add(int x,int y){e[++cnt].to=y;e[cnt].next=head[x] ;head[x]=cnt ;
}
void dfs1(int rt,int fa,int depth){ //主要處理深度，父親和兒子 f[rt]=fa;dep[rt]=depth;size[rt]=1;//一些初始化 for (int i=head[rt];i;i=e[i].next){int to=e[i].to ;if (to==fa) continue ;//保證不是父親 dfs1(to,rt,depth+1) ;size[rt]+=size[to] ;//rt的大小+子樹的大小 if (size[son[rt]]<size[to]) son[rt]=to ;//改變重兒子 }return ;
}
void dfs2(int rt,int t){ //主要處理鏈，dfs序 top[rt]=t;dfn[rt]=++cnt;rk[cnt]=rt;//初始化if (!son[rt]) return ;//該點沒有重兒子 dfs2(son[rt],t) ;//rt的重兒子也是和rt一樣處于以t為頂端的重鏈 for (int i=head[rt];i;i=e[i].next){int to=e[i].to ;if (to!=f[rt] && to!=son[rt]) dfs2(to,to) ;//一個點位于輕鏈底端，那么它的top必然是它本身}return ;
}
struct seg{ //線段樹 int ls,rs,lazy,l,r;int sum ;
}tree[N<<1];
inline void pushup(int rt){tree[rt].sum=(tree[tree[rt].ls].sum+tree[tree[rt].rs].sum+tree[rt].lazy*(tree[rt].r-tree[rt].l+1))%p;return ;
}
void build(int ll,int rr,int rt){ //createif (ll==rr){tree[rt].l=tree[rt].r=ll ;tree[rt].sum=a[rk[ll]] ;return ;}else {int mid=(ll+rr)>>1;tree[rt].ls=cnt++ ;tree[rt].rs=cnt++ ;build(ll,mid,tree[rt].ls) ;build(mid+1,rr,tree[rt].rs) ;tree[rt].l=tree[tree[rt].ls].l ;tree[rt].r=tree[tree[rt].rs].r ;pushup(rt) ;}return ;
}
void update(int l,int r,int rt,int c){ //l~r +c if (l<=tree[rt].l && tree[rt].r<=r) {tree[rt].sum=(tree[rt].sum+c*(tree[rt].r-tree[rt].l+1))%p ;tree[rt].lazy=(tree[rt].lazy+c)%p ;}else {int mid=(tree[rt].l+tree[rt].r)>>1 ;if (l<=mid) update(l,r,tree[rt].ls,c) ;if (mid<r) update(l,r,tree[rt].rs,c) ;pushup(rt) ;}return ;
}
int query(int l,int r,int rt){if (l<=tree[rt].l && tree[rt].r<=r) return tree[rt].sum ;int tot=(tree[rt].lazy*(min(r,tree[rt].r)-max(l,tree[rt].l)+1)%p)%p ;//初始值int mid=(tree[rt].l+tree[rt].r)>>1 ;if (l<=mid) tot=(tot+query(l,r,tree[rt].ls))%p ;if (mid<r)  tot=(tot+query(l,r,tree[rt].rs))%p ;return tot%p ; 
} 
inline int sum(int x,int y){int ans=0;int fx=top[x],fy=top[y] ;while (fx!=fy){if (dep[fx]>=dep[fy]) {ans=(ans+query(dfn[fx],dfn[x],rt))%p ;x=f[fx],fx=top[x] ;}else {ans=(ans+query(dfn[fy],dfn[y],rt))%p ;y=f[fy],fy=top[y] ;}} if (dfn[x]<=dfn[y]) ans=(ans+query(dfn[x],dfn[y],rt))%p ;else ans=(ans+query(dfn[y],dfn[x],rt))%p ;return ans%p ;
}
inline void UPDATE(int x,int y,int c){int fx=top[x],fy=top[y];while(fx!=fy){if(dep[fx]>=dep[fy]){update(dfn[fx],dfn[x],rt,c) ;x=f[fx],fx=top[x];}else {update(dfn[fy],dfn[y],rt,c) ;y=f[fy],fy=top[y];}}if (dfn[x]<=dfn[y]) update(dfn[x],dfn[y],rt,c) ;else update(dfn[y],dfn[x],rt,c) ;return ;
}
main(){scanf("%lld%lld%lld%lld",&n,&m,&r,&p) ;for (int i=1;i<=n;i++) scanf("%lld",&a[i]) ;for (int i=1;i<n;i++){int x,y ;scanf("%lld%lld",&x,&y) ;add(x,y);add(y,x) ;}cnt=0 ;dfs1(r,0,1) ;dfs2(r,r) ;cnt=0;rt=cnt++ ;build(1,n,rt);
//  return 0 ; for (int i=1;i<=m;i++){//   cout<<i<<endl ;int x,y,op ;int z ;scanf("%lld",&op);if (op==1){scanf("%lld%lld%lld",&x,&y,&z) ;UPDATE(x,y,z) ; }else if (op==2){scanf("%lld%lld",&x,&y) ;printf("%lld\n",sum(x,y)) ;}else if (op==3){scanf("%lld%lld",&x,&z) ;update(dfn[x],dfn[x]+size[x]-1,rt,z) ; }else {scanf("%lld",&x) ;printf("%lld\n",query(dfn[x],dfn[x]+size[x]-1,rt)) ;}}
}

再來一道例題。

BZOJ 4196 NOI2015 軟件包管理器

這個問題是動態刪鏈，動態加鏈的過程。

這題其實比上題還簡單，直接維護線段樹即可。

#include <bits/stdc++.h>
using namespace std ;
const int N = 100010 ;
const int inf = (1<<30) ;
#define rep(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define REP(i,a,b) for (int (i)=(a);(i)>=(b);(i)--)
#define ls ((rt)<<1)
#define rs ((rt)<<1|1)typedef long long ll ;vector <int> e[N] ;
int size[N],fa[N],dep[N],top[N],hson[N],dfn[N] ;
int n,m,tot,x ;
char op[20] ;
struct node{int l,r,sum,lazy ;
}tr[N<<2];void dfs1(int rt){size[rt]=1 ;for (int i=0;i<e[rt].size();i++){int to=e[rt][i] ;if (to==fa[rt]) continue ;fa[to]=rt;dep[to]=dep[rt]+1; dfs1(to) ;size[rt]+=size[to] ;if (!hson[rt] || size[to]>size[hson[rt]]) hson[rt]=to ;}
}void dfs2(int rt,int t){top[rt]=t;dfn[rt]=++tot;if (!hson[rt]) return ;dfs2(hson[rt],t) ;for (int i=0;i<e[rt].size();i++){int to=e[rt][i] ;if (to==fa[rt] || to==hson[rt]) continue ;dfs2(to,to) ;}
}
inline void pushup(int rt){tr[rt].sum=tr[ls].sum+tr[rs].sum ;
}
void build(int rt,int l,int r){tr[rt].l=l;tr[rt].r=r,tr[rt].lazy=-1;if (l==r) return ;int mid=(l+r)>>1 ;build(ls,l,mid) ;build(rs,mid+1,r) ;pushup(rt) ;
}
inline void pushdown(int rt){ if (tr[rt].lazy==-1) return ;tr[ls].sum=tr[rt].lazy*(tr[ls].r-tr[ls].l+1) ;tr[rs].sum=tr[rt].lazy*(tr[rs].r-tr[rs].l+1) ;tr[ls].lazy=tr[rt].lazy ;tr[rs].lazy=tr[rt].lazy ;tr[rt].lazy=-1 ;
}
void modify(int rt,int l,int r,int c){  if (l<=tr[rt].l && tr[rt].r<=r) {tr[rt].sum=c*(tr[rt].r-tr[rt].l+1) ;tr[rt].lazy=c ;return ;}pushdown(rt) ; int mid=(tr[rt].l+tr[rt].r)>>1 ;if (l<=mid) modify(ls,l,r,c) ;if (r>mid) modify(rs,l,r,c) ;pushup(rt) ;
}
int query(int rt,int l,int r){if (l<=tr[rt].l && tr[rt].r<=r) return tr[rt].sum ;pushdown(rt) ;int res=0,mid=(tr[rt].l+tr[rt].r)>>1 ;if (l<=mid) res+=query(ls,l,r) ;if (r>mid) res+=query(rs,l,r) ;return res ;
}
int sum(int x){int ans=0,fx=top[x] ;while (fx!=1){ans+=dfn[x]-dfn[fx]-query(1,dfn[fx],dfn[x])+1 ;modify(1,dfn[fx],dfn[x],1) ;x=fa[fx] ;fx=top[x] ;}ans+=dfn[x]-dfn[1]-query(1,dfn[1],dfn[x])+1 ;modify(1,dfn[1],dfn[x],1) ;return ans ;
}
int main(){scanf("%d",&n) ;for (int i=2;i<=n;i++) {scanf("%d",&x) ;x++ ; e[x].push_back(i) ;e[i].push_back(x) ;}fa[1]=0;dep[1]=1 ;dfs1(1) ;dfs2(1,1) ;build(1,1,n) ;scanf("%d",&m) ;for (int i=1;i<=m;i++){scanf("%s%d",&op,&x) ;x++ ;if (op[0]=='i') printf("%d\n",sum(x)) ;else {printf("%d\n",query(1,dfn[x],dfn[x]+size[x]-1)) ;modify(1,dfn[x],dfn[x]+size[x]-1,0) ;}}
}

都理解了， 來幾道習題練練

Aragorn's Story

[HAOI2015]樹上操作

月下“毛景樹”

蒟蒻第一次寫關于算法的博客，有問題或建議請及時提出，在評論區中發表，博主將及時更改，謝謝閱讀！