重链剖分学习笔记

重链剖分学习笔记

Part.1 引入

重链剖分是一种用于解决树上的路径查询和修改问题的算法，他能将 $O(n)$ 级别的操作转换为 $O(\log n)$ 的级别，可以说十分常用。本文将带你深入解析这个算法。

Part.2 概念和思路

在讲解本算法之前，我们先引入一些概念：

• 轻重儿子：对于一个树上的节点 $u$，其儿子中子树大小最大的叫重儿子，其余的叫轻儿子。为了方便理解，我们把根节点算作轻儿子；
• 轻重边：对于一个树上的节点 $u$，连向重儿子的边叫重边，否则就是轻边；
• 重链：从一个轻儿子出发，一直向深处走重边，形成的路径叫做重链。

如上图所示，红色的节点代表重儿子，绿色的节点代表轻儿子，蓝色的方框是一条重链。

由于每个点只有一个重儿子，按照重链一定能把树分成若干个不重不漏的部分。这种算法就叫做重链剖分。

重链剖分有个很好的性质，就是从任意一个点出发向根走，至多经过 $\log n$ 条轻边，也就是至多经过 $\log n$ 条重链。因为对于一个节点 $u$，其重儿子的子树大小一定大于其轻儿子的子树大小，那么意味着从 $u$ 的任何一个轻儿子跳到 $u$，子树大小都会乘 $2$。

那我们如何去实现这个算法呢？

最普遍的就是两边 DFS 法。首先第一遍 DFS 需要确认一个节点的父亲、深度、子树大小、重儿子等信息，第二遍 DFS 确认每个节点所在重链的链顶。如果需要，在第二遍 DFS 中还要确定 DFS 序等信息。

Part.3 代码实现

如果没有搞懂上面在说啥，可以配合代码理解：

int son[N],top[N],f[N],siz[N],dep[N],dfn[N],pre[N],idx;
vector<int> g[N];
void dfs1(int u,int fa)
{
	f[u] = fa,dep[u] = dep[fa]+1,siz[u] = 1;//确定父亲、深度
	for(auto v:g[u])
	{
		if(v==fa) continue;
		dfs1(v,u),siz[u]+=siz[v];//确定子树大小
		if(siz[son[u]]<siz[v]||son[u]==0) son[u] = v;//确定重儿子
	}
}
void dfs2(int u,int tp)//tp就是当前节点所在重链的链顶
{
	dfn[u] = ++idx,top[u] = tp,pre[idx] = u;//DFS序，链顶
	if(son[u]==0) return;//连重儿子都没有，怎么可能有儿子
	dfs2(son[u],tp);//往重儿子走，链顶不变
	for(auto v:g[u])
	{
		if(v==f[u]||v==son[u]) continue;
		dfs2(v,v);//往轻儿子走，形成新的重链
	}
}

Part.4 应用

上面的对解题没啥大用，接下来，正片开始。

1.树剖求 LCA

树剖求 LCA 其实是一个非常经典的应用。我们从两个节点出发，每次选一个点，跳到他所在链顶的父亲节点上，知道两个点在同一条重链为之。那关键是我们选那个点呢？总不能随机数吧。

我们可以发现，深度越小（即越靠近树根）的点越容易成为 LCA，所以每次我们选一个链顶深度大的节点开始跳。这样，我们就能保证正确性了。

当两个点在同一条重链是，深度小的就是 LCA，返回即可。代码如下：

int lca(int x,int y)
{
    while(top[x]!=top[y])//不在一条链上
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);//跳链顶深度大的点
        x = f[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);//返回深度小的点
    return x;
}

2.树剖维护路径、子树信息

其实和求 LCA 的区别不大。再求 LCA 的过程中，我们把路径上的点拆成若干条重链。而在一条重链上，节点的 DFS 序是连续的。所以考虑对 DFS 序建立数据结构（比如线段树）。

至于维护子树信息，是一样的，因为子树内 DFS 序也是一段连续的区间。

具体的，我们来看看 P3384 怎么实现。

#include <bits/stdc++.h>
#define int long long //开个 long long
#define ls (k*2)
#define rs (k*2+1)
using namespace std;
//快读快写
template<typename T> inline void read(T &x)
{
	x = 0;
	T f = 1;char ch = getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
		{
			f = -1,ch = getchar();
			break;
		}
		ch = getchar();
	}
	while(ch>='0'&&ch<='9')
		x = (x<<3)+(x<<1)+ch-48,ch = getchar();
	x*=f;
}
template<typename T> inline T read()
{
	T x;read(x);return x;
}
template<typename T> inline void write(T x)
{
    if(x<0) x = -x,putchar('-');
    if(x<=9) return putchar(x+48),void();
    write(x/10);
    putchar(x%10+48);
}
template<typename T> inline void writen(T x)
{
    write(x);
    puts("");
}
const int N = 1e5+5; 
int n,q,mod,rt;
int son[N],top[N],f[N],siz[N],dep[N],dfn[N],pre[N],w[N],idx;
vector<int> g[N];
//区间加、区间求和线段树板子
struct node{
	int val,tag;
	friend node operator + (node x,node y)
	{
		node res;
		res.val = (x.val+y.val)%mod;
		res.tag = 0;
		return res;
	}
}t[N*4];
void pushup(int k)
{
	t[k] = t[ls]+t[rs];
}
void down(int k,int l,int r,int mid)
{
	if(!t[k].tag) return;
	(t[ls].val+=t[k].tag*(mid-l+1))%=mod,(t[rs].val+=t[k].tag*(r-mid))%=mod;
	(t[ls].tag+=t[k].tag)%=mod,(t[rs].tag+=t[k].tag)%=mod;
	t[k].tag = 0;
}
void build(int k,int l,int r)
{
	if(l==r)
	{
		t[k].val = w[pre[l]];
		return;
	}
	int mid = (l+r)/2;
	build(ls,l,mid),build(rs,mid+1,r);
	pushup(k);
}
void change(int k,int l,int r,int x,int y,int v)
{
	if(l>y||r<x) return;
	if(l>=x&&r<=y)
	{
		t[k].val+=v*(r-l+1),t[k].tag+=v;
		return;
	}
	int mid = (l+r)/2;
	down(k,l,r,mid);
	change(ls,l,mid,x,y,v),change(rs,mid+1,r,x,y,v);
	pushup(k);
}
int ask(int k,int l,int r,int x,int y)
{
	if(l>y||r<x) return 0;
	if(l>=x&&r<=y) return t[k].val;
	int mid = (l+r)/2;
	down(k,l,r,mid);
	return ask(ls,l,mid,x,y)+ask(rs,mid+1,r,x,y); 
}
//重链剖分
void dfs1(int u,int fa)
{
	f[u] = fa,dep[u] = dep[fa]+1,siz[u] = 1;//确定父亲、深度
	for(auto v:g[u])
	{
		if(v==fa) continue;
		dfs1(v,u),siz[u]+=siz[v];//确定子树大小
		if(siz[son[u]]<siz[v]||son[u]==0) son[u] = v;//确定重儿子
	}
}
void dfs2(int u,int tp)//tp就是当前节点所在重链的链顶
{
	dfn[u] = ++idx,top[u] = tp,pre[idx] = u;//DFS序，链顶
	if(son[u]==0) return;//连重儿子都没有，怎么可能有儿子
	dfs2(son[u],tp);//往重儿子走，链顶不变
	for(auto v:g[u])
	{
		if(v==f[u]||v==son[u]) continue;
		dfs2(v,v);//往轻儿子走，形成新的重链
	}
}
void changetree(int x,int y,int v)
{
	v%=mod;
	while(top[x]!=top[y])//不在一条链上
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);//跳链顶深度大的点
		change(1,1,n,dfn[top[x]],dfn[x],v),x = f[top[x]];//修改一整个重链
	}
	if(dep[x]>dep[y]) swap(x,y);//深度小的点为 LCA
	change(1,1,n,dfn[x],dfn[y],v);//修改最后重链的一部分
}
int asktree(int x,int y)
{
	int res = 0;
	while(top[x]!=top[y])//不在一条链上
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);//跳链顶深度大的点
		(res+=ask(1,1,n,dfn[top[x]],dfn[x]))%=mod,x = f[top[x]];//查询一整个重链
	}
	if(dep[x]>dep[y]) swap(x,y);//深度小的点为 LCA
	(res+=ask(1,1,n,dfn[x],dfn[y]))%=mod;//查询最后重链的一部分
	return res;
}
//主函数
signed main()
{
	read(n),read(q),read(rt),read(mod);
	for(int i = 1;i<=n;i++)
		read(w[i]);
	for(int i = 1,u,v;i<n;i++)
		read(u),read(v),g[u].push_back(v),g[v].push_back(u);
	dfs1(rt,0),dfs2(rt,rt);
	build(1,1,n);
	while(q--)
	{
		int op,x,y,z;
		read(op),read(x);
		if(op==1)
		{
			read(y),read(z);
			changetree(x,y,z);
		}
		else if(op==2)
		{
			read(y);
			writen(asktree(x,y)%mod);
		}
		else if(op==3) read(y),change(1,1,n,dfn[x],dfn[x]+siz[x]-1,y%mod);
		else writen(ask(1,1,n,dfn[x],dfn[x]+siz[x]-1)%mod);
	}
	return 0;
}

---

讲完啦！码字不易，给个赞吧！
$$\text{THE?END}$$