浅谈树链剖分（重链剖分）
一、算法简介
树链剖分是一种用于树上路径修改与求和的一种算法，
其核心原理是将链分为轻重，并通过轻重链的跳跃实现简便处理。
二、术语解释
1、重（轻）子节点：
子树大小最大的子节点被称为重子节点，除了重儿子以外的子节点均为轻子节点。
2、重（轻）链：
重子节点相连形成的链被称为重链，轻子节点对应的链则为轻链。
重链上的dfs序连续。
3、链顶点：
一条链中深度最浅的点被称为链顶点，链顶点可以用于整条链的标识
tips：重轻链的概念是相对的，每一条轻链作为重链时链顶点均为本身
三、具体实现
可以通过两次dfs实现：
第一次处理出重子节点等节点间关系的内容，
第二次处理出DFS序和链相关的内容，并处理出链上内容
在查询LCA（最近公共祖先）时，
若两点不在同一条链上（链顶点不同），
则将链顶点深度较深的点往上一条链跳，
直到两点在同一条链上。
由于dfs序的连续性，
可以直接在线性数据结构上维护（如线段树、树状数组等）。
四、用处
可用于快速求LCA并处理两点简单距离，
进行查询和修改。
模板题P3384
五、标准程序
线段树版本:
#include<iostream>
#include<vector>
using namespace std;
const int MAXN=100005;
int a,b,c,modd,tot=0,t=0;
int num[MAXN],lct[MAXN],tag[MAXN<<2],dep[MAXN<<2],node[MAXN<<2];
//num点权 lctDFS序上点权 tag延迟标记 dep线段树宽度 node线段树点权
int fa[MAXN],dpt[MAXN],top[MAXN];
//fa父节点 dpt点深度 top链顶点
int hson[MAXN],dfn[MAXN],size_[MAXN];
//hson重子节点 dfnDFS序编号 size_子树宽度
struct edges
{
int ends,to;
};
edges edge[MAXN<<1];
int head[MAXN];
inline char bit()
{
static char buf[1000005],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100005,stdin),p1==p2)?EOF:*p1++;
}//文件读入流，相当于getchar()
inline int read()
{
char x=bit();int t=0;
while(!isdigit(x))x=bit();
while(isdigit(x))t=(t<<3)+(t<<1)+x-'0',x=bit();
return t;
}//快速读入
inline void init(int x)
{
size_[x]=1,hson[x]=0;
//如果是叶子节点也有自己本身的深度1,重子节点开始先初始化为0
for(register int i=head[x];i;i=edge[i].to)
{
int now=edge[i].ends;
if(now==fa[x])continue;
fa[now]=x;//父节点处理出来防止死循环
dpt[now]=dpt[x]+1;//深度先处理出来
init(now);
size_[x]+=size_[now];//扫完子树后更新子树大小
if(size_[now]>size_[hson[x]])hson[x]=now;
//更新真正子树最大的节点，即重子节点
}
}
inline void build(int x,int k)
{
dfn[x]=++tot,lct[tot]=num[x];
//处理DFS序，并把点权映射到DFS序上
top[x]=k;//处理出顶点
if(hson[x])build(hson[x],k);
//优先扫重子节点，保证重链DFN序的连续性
for(register int i=head[x];i;i=edge[i].to)
{
int now=edge[i].ends;
if(now==fa[x]||now==hson[x])continue;
build(now,now);
//轻子节点的链顶点为自己本身
}
}
inline void binary_tree(int k,int l,int r)
{
dep[k]=r-l+1;
if(l==r)
{
node[k]=lct[l];
return;
}
int mid=(l+r)>>1;
binary_tree(k<<1,l,mid);
binary_tree(k<<1|1,mid+1,r);
(node[k]=node[k<<1]+node[k<<1|1])%=modd;
}//预处理线段树
inline void update(int k)
{
(node[k<<1]+=dep[k<<1]*tag[k])%=modd;
(node[k<<1|1]+=dep[k<<1|1]*tag[k])%=modd;
(tag[k<<1]+=tag[k])%=modd;
(tag[k<<1|1]+=tag[k])%=modd;
tag[k]=0;
}//下传延迟标记
/*注意！延迟标记维护的点已经更新过了，所以在下传的时候不需要更新自身*/
inline void add(int k,int l,int r,int x,int y,int z)
{
if(x<=l&&r<=y)
{
node[k]+=z*dep[k];
tag[k]+=z;
//如果包含在查询范围内，可以直接更新
return;
}
update(k);
int mid=(l+r)>>1;
if(x<=mid)add(k<<1,l,mid,x,y,z);
if(y>mid)add(k<<1|1,mid+1,r,x,y,z);
node[k]=node[k<<1]+node[k<<1|1];
}//线段树更新
inline int findx(int k,int l,int r,int x,int y)
{
if(x<=l&&r<=y)return node[k]%modd;
update(k);
int mid=(l+r)>>1,query=0;
if(x<=mid)(query+=findx(k<<1,l,mid,x,y))%=modd;
if(y>mid)(query+=findx(k<<1|1,mid+1,r,x,y))%=modd;
return (query%=modd);
}//线段树查询
inline void change_line(int x,int y,int z)
{
z%=modd;
while(top[x]!=top[y])
{
if(dpt[top[x]]<dpt[top[y]])x^=y,y^=x,x^=y;
add(1,1,a,dfn[top[x]],dfn[x],z);
x=fa[top[x]];
//保证链顶节点深度深的向上传，因为点是跳到链顶节点的父节点的
}
if(dpt[x]>dpt[y])x^=y,y^=x,x^=y;
add(1,1,a,dfn[x],dfn[y],z);
}//修改两点简单路径
inline int find_line(int x,int y)
{
int query=0,memory;
while(top[x]!=top[y])
{
if(dpt[top[x]]<dpt[top[y]])x^=y,y^=x,x^=y;
memory=findx(1,1,a,dfn[top[x]],dfn[x]);
(query+=memory)%=modd;
x=fa[top[x]];
//整条链可以直接处理
}
if(dpt[x]>dpt[y])x^=y,y^=x,x^=y;
memory=findx(1,1,a,dfn[x],dfn[y]);
query+=memory;
return query%modd;
}
int main()
{
a=read();b=read();c=read();modd=read();
for(register int i=1;i<=a;++i)num[i]=read();
for(register int i=1;i<a;++i)
{
int x,y;
x=read();y=read();
edge[++t]={y,head[x]},head[x]=t;
edge[++t]={x,head[y]},head[y]=t;
}
dpt[c]=1;
init(c);build(c,c);
binary_tree(1,1,a);
for(register int i=1;i<=b;++i)
{
int opt,x,y,z,res=0;
opt=read();x=read();
switch(opt){
case 1:
y=read();z=read();
change_line(x,y,z);
break;
case 2:
y=read();
printf("%d\n",find_line(x,y)%modd);
break;
case 3:
z=read();
add(1,1,a,dfn[x],dfn[x]+size_[x]-1,z);
break;
case 4:
printf("%d\n",(findx(1,1,a,dfn[x],dfn[x]+size_[x]-1))%modd);
break;
}
}
return 0;
}
树状数组版本
#include<iostream>
#define swap(x,y) x^=y,y^=x,x^=y;
#define ll long long
#define lowbit(x) x&(-x)
//补码的形式为取反
using namespace std;
const int MAXN=100005;
int a,b,c,modd,tot=0,cnt=0;
//tot记dfn,cnt记链式前向星
int fa[MAXN],size_[MAXN],dpt[MAXN];
//fa父节点,size_子树大小,dpt结点深度
int dfn[MAXN],top[MAXN],hson[MAXN];
//dfnDFS序,top链顶节点,hson重儿子
int lct[MAXN],head[MAXN];
//lctDFS序上点权,head链式前向星用
ll num[MAXN],node[MAXN],sum[MAXN];
//num点权,nodeDFS序上树状数组点权,sum同node,用于计算区间和
/*如果不知道如何树状数组算区间和可以去网上搜搜
思路是推出公式ans=(x+1)*Σnum[i]-Σsum[i] */
struct edges
{
int ends,to;
};edges edge[MAXN<<1];
//链式前向星
inline char bit(){
static char buf[1000005],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}//文件流读入,用于替换getchar函数加速
inline int read(){
//#define bit() getchar()
//把define前注释去掉即可手动输入
char x=bit();int t=0;
while(!isdigit(x))x=bit();
while(isdigit(x))t=(t<<3)+(t<<1)+x-'0',x=bit();
return t;
}//快速读入
void dfs1(int x)
{
size_[x]=1,hson[x]=0;
for(int i=head[x];i;i=edge[i].to)
{
int now=edge[i].ends;
if(fa[x]==now)continue;
//防止回传导致DFS卡死
fa[now]=x;
dpt[now]=dpt[x]+1;
//预处理父节点和深度
dfs1(now);
size_[x]+=size_[now];
//处理完子树后可得子树大小
hson[x]=size_[now]>size_[hson[x]]?now:hson[x];
//重儿子定义为子树大小最大的儿子
/*以上表达方式为三目运算符,?前为条件
结果为true则返回:前的值，否则返回:后的值*/
}
}//第一次DFS,用于寻找重儿子及处理其他信息
void dfs2(int x,int y)
{
dfn[x]=++tot,lct[tot]=num[x],top[x]=y;
if(hson[x])dfs2(hson[x],y);
//重儿子连在原来的链上
for(int i=head[x];i;i=edge[i].to)
{
int now=edge[i].ends;
if(now==fa[x]||now==hson[x])continue;
dfs2(now,now);
/*轻儿子为所有非重儿子的儿子,
则其自身可构成另一条链，
且链顶点为自身*/
}
}//第二次DFS,用于处理DFS序及重链,并讲
inline void add(int x,int query){
for(register int i=x;i<=a;i+=lowbit(i))
node[i]+=(ll)query,sum[i]+=(ll)x*query;
}//树状数组更新
inline ll get_val(int x){
ll ans=0;
for(register int i=x;i;i-=lowbit(i))
ans+=(ll)(x+1)*node[i]-sum[i];
return ans;
}//树状数组查询
void change_line(int x,int y,int query)
{
while(top[x]!=top[y])//跳到同一条链为止
{
if(dpt[top[x]]<dpt[top[y]])swap(x,y);
/*优先选择链深度较深的点往上跳
*/
add(dfn[top[x]],query);
add(dfn[x]+1,-query);
x=fa[top[x]];
}
if(dpt[x]>dpt[y])x^=y,y^=x,x^=y;
add(dfn[x],query);add(dfn[y]+1,-query);
}//修改x,y两点路径上的点
ll get_line(int x,int y)
{
ll ans=0;
while(top[x]!=top[y])
{
if(dpt[top[x]]<dpt[top[y]])swap(x,y);
ans+=get_val(dfn[x])-get_val(dfn[top[x]]-1);
x=fa[top[x]];
}
if(dpt[x]>dpt[y])swap(x,y);
(ans+=get_val(dfn[y])-get_val(dfn[x]-1));
return ans;
}//同理
int main()
{
a=read();b=read();c=read();modd=read();
for(register int i=1;i<=a;++i)num[i]=read();
for(register int i=1;i<a;++i)
{
int x,y;x=read();y=read();
edge[++cnt]={y,head[x]},head[x]=cnt;
edge[++cnt]={x,head[y]},head[y]=cnt;
}
dpt[c]=1;
dfs1(c);dfs2(c,c);
for(register int i=1;i<=a;++i)add(i,lct[i]-lct[i-1]);
while(b--)
{
int opt,x,y,z;
opt=read();x=read();
switch(opt){
case 1:
y=read();z=read();
change_line(x,y,z);
break;
case 2:
y=read();
printf("%lld\n",get_line(x,y)%modd);
break;
case 3:
z=read();
add(dfn[x],z);add(dfn[x]+size_[x],-z);
break;
case 4:
printf("%lld\n",(get_val(dfn[x]+size_[x]-1)-get_val(dfn[x]-1))%modd);
break;
}
}
return 0;
}
六、总结
除修改两点简单路径时间复杂度为 O(log2n)
其他操作的时间复杂度为 O(logn) 。
证明：根据重链的定义可知，重链占子树节点的一半以上，
则每次向上查询都会减半，减少的次数正好是 log2n 。
总而言之，树链剖分不像是一种独立的算法，更像是一种思想，
它强调了dfn对非线性结构的线性优化作用，
能够使得树上维护更为简便、快捷。
本文是原创文章，转载请注明来自 爱特工作室
阅读建议
评论
匿名评论
隐私政策
你无需删除空行，直接评论以获取最佳展示效果
