树链剖分（重链剖分）

大家好，欢迎来到IT知识分享网。

前言

本文主要针对于还没有学习过这个算法的新手同学，因为我也刚学 。
最好要先知道DFN序，LCA是什么。

一、什么是树链剖分，是干什么的？

二、一般的树链剖分操作（重链剖分）

1.前置知识

定义 轻子节点 表示剩余的所有子结点。

从这个结点到重子节点的边为 重边。

到其他轻子节点的边为 轻边。

若干条首尾衔接的重边构成 重链。

把落单的结点也当作重链，那么整棵树就被剖分成若干条重链。

int top[N],siz[N],hson[N]; //top用来记录每条重链的头节点 //siz表示这个点的子树大小 //hson[x]表示x节点的重儿子是谁 void dfs1(int x,int f) { siz[x]=1; for(int i=0;i<g[x].size();++i) { int v=g[x][i]; if(v==f) continue; dfs1(v,x); siz[x]+=siz[v]; if(siz[hson[x]]<siz[v]) hson[x]=v; } } 

树上每个节点都属于且仅属于一条重链。

重链开头的结点不一定是重子节点（因为重边是对于每一个结点都有定义的）。

所有的重链将整棵树 完全剖分。

在剖分时 重边优先遍历，最后树的 DFS 序上，重链内的 DFS 序是连续的。按 DFN 排序后的序列即为剖分后的链。（如果还不了解DFN序的建议去了解一下再看）。
因此对于一个点如果他有重儿子就先遍历它的重儿子，然后回溯回去如果还有其它不是重儿子的点再接着走这个点，然后这个点有重儿子再先走它的重儿子…具体看代码：

void dfs2(int x,int tp) { top[x]=tp; if(hson[x]) { dfs2(hson[x],tp); } for(int i=0;i<g[x].size();++i) { int v=g[x][i]; if(v==fa[x]||v==hson[x]) continue; dfs2(v,v); } } 

至此树链剖分的基本操作就结束了，但是这有什么用？划分完了我们用来干嘛？

2.树链剖分求LCA

怎么利用树剖来求LCA（最近公共祖先）呢?

不断向上跳重链，当跳到同一条重链上时，深度较小的结点即为 LCA。

向上跳重链时需要先跳所在重链顶端深度较大的那个。
在这个求LCA的过程中“向上跳”就是我们树链剖分的精髓所在了。(虽然向上跳的方式和倍增不同，但如果理解了倍增可能会对这个过程理解的更快)。
具体过程就是：首先判断两个点在不在一条重链上，如果不在的话，我们让头节点深度大（更往下）的那个点向上跳到他头节点的父节点（这里自己结合上面的图片想一想会更好理解），然后当跳到一条链上的时候深度较小的点就是他们的LCA。

#include<iostream> #include<math.h> #include<string.h> #include<vector> #include<queue> #include<algorithm> #include<set> #include<stack> #include<map> #include<unordered_map> #define debug(a) cout<<"*"<<a<<"*\n" using namespace std; typedef long long ll; #define INF 0x3f3f3f3f constexpr int N=5e5+10; constexpr int mod=1e9+7; int n,m,root; vector<int>g[N]; int top[N],siz[N],hson[N],dep[N],fa[N]; void dfs1(int x,int f) { siz[x]=1; fa[x]=f; dep[x]=dep[f]+1; for(int i=0;i<g[x].size();++i) { int v=g[x][i]; if(v==f) continue; dfs1(v,x); siz[x]+=siz[v]; if(siz[hson[x]]<siz[v]) hson[x]=v; } } void dfs2(int x,int tp) { top[x]=tp; if(hson[x]) { dfs2(hson[x],tp); } for(int i=0;i<g[x].size();++i) { int v=g[x][i]; if(v==fa[x]||v==hson[x]) continue; dfs2(v,v); } } int lca(int a,int b) { while(top[a]!=top[b]) { if(dep[top[a]]<dep[top[b]]) swap(a,b); a=fa[top[a]]; } return dep[a]<dep[b]?a:b; } int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>m>>root; for(int i=1;i<=n-1;++i) { int u,v;cin>>u>>v; g[u].emplace_back(v); g[v].emplace_back(u); } dfs1(root,0); dfs2(root,root); for(int i=1;i<=m;++i) { int u,v;cin>>u>>v; cout<<lca(u,v)<<'\n'; } return 0; } 

3.用其他数据结构来维护

这个时候我们已经对树链剖分有一个基本的认识了，那么怎么做到的前面说的用其他数据结构去维护呢?
这个时候DFN序就起了很大的作用了，如果已经对DFN序有了解的话那么应该已经知道了对于一颗子树上的DFN序是连续的。（不了解也别怕，DFN序就是按照dfs的顺序跑一遍给节点一个标号 ）。
那么如果对于每次操作都更改子树的话我们是不是就可以利用这个DFN序去建一个数据结构（比如线段树）去维护上面的操作呢，比如说将一个号码的全部子树都加或减去一个数字，我们就可以用DFN序的连续性用线段树来 维护，那么如果换一下问题不是全部子树，而是从x点到y点呢？
我们来想一下，这个时候就可以用到我们的树剖。

#include<iostream> #include<math.h> #include<string.h> #include<vector> #include<queue> #include<algorithm> #include<set> #include<stack> #include<map> #include<unordered_map> #define debug(a) cout<<"*"<<a<<"*\n" using namespace std; typedef long long ll; #define int long long #define INF 0x3f3f3f3f constexpr int N=2e5+10; constexpr int mod=1e9+7; struct Node { int sum,l,r,lz; }tree[N<<2]; vector<int>g[N]; int a[N],dfn[N],todfn[N],dep[N],fa[N],siz[N],hson[N],top[N]; int n,m,r,p; int id; void dfs1(int x,int f) { siz[x]=1; fa[x]=f; dep[x]=dep[f]+1; for(int i=0;i<g[x].size();++i) { if(g[x][i]!=f) { dfs1(g[x][i],x); siz[x]+=siz[g[x][i]]; if(siz[hson[x]]<=siz[g[x][i]]) hson[x]=g[x][i]; } } } void dfs2(int x,int tp) { top[x]=tp; dfn[x]=++id; todfn[id]=x; if(hson[x]) dfs2(hson[x],tp); else return; for(int i=0;i<g[x].size();++i) { if(g[x][i]==fa[x]||g[x][i]==hson[x]) continue; dfs2(g[x][i],g[x][i]); } } void push_up(ll i) { tree[i].sum=(tree[i<<1].sum%p+tree[i<<1|1].sum%p)%p; } void build(ll i,ll l,ll r) { tree[i].l=l; tree[i].r=r; if(l==r) { tree[i].sum=a[todfn[l]]%p; return; } int mid=(l+r)>>1; build(i<<1,l,mid); build(i<<1|1,mid+1,r); push_up(i); } void push_down(ll i) { if(tree[i].lz) { tree[i<<1].sum=(tree[i<<1].sum%p+(tree[i].lz%p*(tree[i<<1].r-tree[i<<1].l+1))%p)%p; tree[i<<1|1].sum=(tree[i<<1|1].sum%p+(tree[i].lz%p*(tree[i<<1|1].r-tree[i<<1|1].l+1))%p)%p; tree[i<<1].lz=(tree[i<<1].lz%p+tree[i].lz%p)%p; tree[i<<1|1].lz=(tree[i<<1|1].lz%p+tree[i].lz%p)%p; tree[i].lz=0; } } void add(ll i,ll l,ll r,ll k) { if(tree[i].l>=l&&tree[i].r<=r) { tree[i].sum=(tree[i].sum%p+k%p*(tree[i].r-tree[i].l+1)%p)%p; tree[i].lz=(tree[i].lz%p+k%p)%p; return; } push_down(i); int mid=(tree[i].l+tree[i].r)>>1; if(l<=mid) add(i<<1,l,r,k); if(r>=mid+1) add(i<<1|1,l,r,k); push_up(i); } ll query(ll i,ll l,ll r) { ll ans=0; if(tree[i].l>=l&&tree[i].r<=r) { return tree[i].sum%p; } push_down(i); int mid=(tree[i].r+tree[i].l)>>1; if(l<=mid) ans=(ans%p+query(i<<1,l,r)%p)%p; if(r>=mid+1) ans=(ans%p+query(i<<1|1,l,r)%p)%p; return ans; } void update(ll x,ll y,ll z) { while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); add(1,dfn[top[x]],dfn[x],z); x=fa[top[x]]; } if(dep[x]<dep[y]) swap(x,y); add(1,dfn[y],dfn[x],z); } ll get(ll x,ll y) { ll ans=0; while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); ans=(ans%p+query(1,dfn[top[x]],dfn[x])%p)%p; x=fa[top[x]]; } if(dep[x]<dep[y]) swap(x,y); ans=(ans%p+query(1,dfn[y],dfn[x])%p)%p; return ans; } signed main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>m>>r>>p; for(int i=1;i<=n;++i) { cin>>a[i]; } for(int i=1;i<=n-1;++i) { int u,v; cin>>u>>v; g[u].emplace_back(v); g[v].emplace_back(u); } dfs1(r,0); dfs2(r,r); build(1,1,n); while(m--) { ll op,x,y,z; cin>>op; if(op==1) { cin>>x>>y>>z; update(x,y,z); }else if(op==2) { cin>>x>>y; cout<<get(x,y)<<'\n'; }else if(op==3) { cin>>x>>z; add(1,dfn[x],dfn[x]+siz[x]-1,z); }else if(op==4) { cin>>x; cout<<query(1,dfn[x],dfn[x]+siz[x]-1)<<'\n'; } } return 0; } 

4.时间复杂度

可以发现，当我们向下经过一条 轻边 时，所在子树的大小至少会除以二。

因此，对于树上的任意一条路径，把它拆分成从 LCA 分别向两边往下走，分别最多走 [O(log n)] 次，因此，树上的每条路径都可以被拆分成不超过 [O(log n)] 条重链。