树链剖分
树链剖分
将树转化为数据结构，便于维护树上信息。
include: 重链剖分，长链剖分，实链剖分（Link Cut Tree）。
注：此文默认读者已经熟悉线段树的基本操作，不熟悉这可以先看这个：
重链剖分
剖树
- 建图
很普通的邻接表存图：
void ins(int x,int y)
{
nex[++cnt]=fir[x];
poi[cnt]=y;
fir[x]=cnt;
}
-
通过第一遍
dfs，统计出每个节点的：-
父节点
fa -
深度
dep -
以当前节点为根的子树大小
siz -
当前节点所有子节点对应的子树中 siz 最大的节点，即重儿子
son
-
int fa[inf],siz[inf],dep[inf],son[inf];
void dfs1(int now,int from)
{
fa[now]=from;siz[now]=1;
dep[now]=dep[from]+1;
int maxn=0;
for(int i=fir[now];i;i=nex[i])
{
int p=poi[i];
if(p==from)continue;
dfs1(p,now);
siz[now]+=siz[p];
if(siz[p]>maxn)
maxn=siz[p],son[now]=p;
}
}
-
然后用第二遍
dfs，统计出：-
每条链的顶点
top -
节点的 dfs 序
dfn -
dfn 所对应的节点号
rnk，即rnk[dfn[x]]=x
第二次
dfs中，在确保深度优先的前提下，以重儿子优先搜索，以确保每条重链的 dfn 是连续的。 -
int top[inf],dfn[inf],rnk[inf],sum;
void dfs2(int now,int topn)
{
top[now]=topn;
dfn[now]=++sum;rnk[sum]=now;
if(son[now]==0)return;
dfs2(son[now],topn);
for(int i=fir[now];i;i=nex[i])
{
int p=poi[i];
if(p==fa[now]||p==son[now])continue;
dfs2(p,p);
}
}
- 效果展示
经过两次 dfs ，就将一棵树上的点按照 dfn 映射到了一个线性的序列上了。
如下边这棵树：
两次 dfs 之后这个树就是：
点中的数表示 dfs 序；红色的边表示重链，黑色的边表示轻链。
映射到线性序列，然后就可以用各种各样的数据结构（如线段树，珂朵莉树）来维护这个序列了。
luogu 模板
题目中包括 4 个操作：
-
1 x y z表示将树上从 \(x\) 到 \(y\) 节点的最短路径上的节点权值都加上 \(z\) 。 -
2 x y表示查询树上从 \(x\) 到 \(y\) 节点的最短路径上的节点权值之和。 -
3 x z表示将树上以 \(x\) 为根的子树上所有节点的权值都加上 \(z\) 。 -
4 x表示查询树上以 \(x\) 为根的子树上所有节点的权值之和。
可以分为两种：子树操作和链上操作。
- 子树操作
观察上图，可以发现，同一子树上的点的 dfn 是连续的。也就是说，同一子树上的点在序列上也是连续的。举个例子：以 11 为根的子树的 siz 是 4，子树对应的 dfn 是从 11 到 14（即 11+4-1）。那么便可以直接进行区间维护。
Code:
void update(int i,int l,int r,int k)
{
if(l<=tre[i].le&&tre[i].ri<=r)
{
tre[i].val+=k*(tre[i].ri-tre[i].le+1);
tre[i].add+=k;tre[i].add%=mod;
tre[i].val%=mod;
return;
}
if(tre[i].add)pushdown(i);
int mid=(tre[i].le+tre[i].ri)>>1;
if(l<=mid)update(i<<1,l,r,k);
if(mid>1,ans=0;
if(l<=mid)ans+=ask(i<<1,l,r),ans%=mod;
if(mid - 链上操作
lca，即 Least Common Ancestors（最近公共祖先），如上图中 2 和 13 的 lca 是 1，5 和 6 的 lca 是 2。
在树上两点的最短路径必然经过 lca ，而且由于重儿子优先搜索，同一条重链上的点的 dfn 也是连续的（如图上的 1,2,3,4，8,9,10 等）。那么就可以在跳 lca 的过程中维护经过的重链上的点。
树剖求 lca 的过程是：
选择两点中 top（重链顶点）深度较大的一个，跳到 top 的 fa 节点，直到两点的 top 相同（即处在同一条重链
），此时深度较小的即为两点的 lca。
Code:
void chain_add(int x,int y,int k)
{
while(top[x]!=top[y])
{
if(dep[top[x]]dep[y])swap(x,y);
update(1,dfn[x],dfn[y],k);
}
int chain_ask(int x,int y)
{
int ans=0;
while(top[x]!=top[y])
{
if(dep[top[x]]dep[y])swap(x,y);
return ans+ask(1,dfn[x],dfn[y])%mod;
}
完整代码:
#include
using namespace std;
int re()
{
int s=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
s=s*10+ch-48,ch=getchar();
return s*f;
}
void wr(int s)
{
if(s<0)putchar('-'),s=-s;
if(s>9)wr(s/10);
putchar(s%10+48);
}
const int inf=1e5+7;
int n,m,root,mod,op,x,y,l,r,k;
int a[inf];
int fir[inf],nex[inf<<1],poi[inf<<1],cnt;
void ins(int x,int y)
{
nex[++cnt]=fir[x];
poi[cnt]=y;
fir[x]=cnt;
}
int fa[inf],siz[inf],dep[inf],son[inf];
void dfs1(int now,int from)
{
fa[now]=from;siz[now]=1;
dep[now]=dep[from]+1;
int maxn=0;
for(int i=fir[now];i;i=nex[i])
{
int p=poi[i];
if(p==from)continue;
dfs1(p,now);
siz[now]+=siz[p];
if(siz[p]>maxn)
maxn=siz[p],son[now]=p;
}
}
int top[inf],dfn[inf],rnk[inf],sum;
void dfs2(int now,int topn)
{
top[now]=topn;
dfn[now]=++sum;rnk[sum]=now;
if(son[now]==0)return;
dfs2(son[now],topn);
for(int i=fir[now];i;i=nex[i])
{
int p=poi[i];
if(p==fa[now]||p==son[now])continue;
dfs2(p,p);
}
}
void swap(int &a,int &b){a^=b^=a^=b;}
struct a_tree{
int le,ri;
int add,val;
}tre[inf<<2];
void build(int i,int l,int r)
{
tre[i].le=l;tre[i].ri=r;
if(l==r)
{
tre[i].val=a[rnk[l]]%mod;
return;
}
int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
tre[i].val=(tre[i<<1].val+tre[i<<1|1].val)%mod;
}
void pushdown(int i)
{
tre[i<<1].val+=tre[i].add*(tre[i<<1].ri-tre[i<<1].le+1);
tre[i<<1|1].val+=tre[i].add*(tre[i<<1|1].ri-tre[i<<1|1].le+1);
tre[i<<1].val%=mod;tre[i<<1|1].val%=mod;
tre[i<<1].add+=tre[i].add;
tre[i<<1|1].add+=tre[i].add;
tre[i<<1].add%=mod;tre[i<<1|1].add%=mod;
tre[i].add=0;
}
void update(int i,int l,int r,int k)
{
if(l<=tre[i].le&&tre[i].ri<=r)
{
tre[i].val+=k*(tre[i].ri-tre[i].le+1);
tre[i].add+=k;tre[i].add%=mod;
tre[i].val%=mod;
return;
}
if(tre[i].add)pushdown(i);
int mid=(tre[i].le+tre[i].ri)>>1;
if(l<=mid)update(i<<1,l,r,k);
if(middep[y])swap(x,y);
update(1,dfn[x],dfn[y],k);
}
int ask(int i,int l,int r)
{
if(l<=tre[i].le&&tre[i].ri<=r)
return tre[i].val;
if(tre[i].add)pushdown(i);
int mid=(tre[i].le+tre[i].ri)>>1,ans=0;
if(l<=mid)ans+=ask(i<<1,l,r),ans%=mod;
if(middep[y])swap(x,y);
return ans+ask(1,dfn[x],dfn[y])%mod;
}
int main()
{
n=re();m=re();root=re();mod=re();
for(int i=1;i<=n;i++)
a[i]=re();
for(int i=1;i 当然，树剖不一定只用线段树，其他的数据结构可是可以的，常用的还有 分块 和 珂朵莉树。
练习
winner @Liu_Kevin 的 树剖题单