【算法笔记】树链剖分

【算法笔记】树链剖分

*强烈建议在阅读本文之前已经掌握前置知识 线段树,如果你没有,请先阅读这篇文章*

不知道树是什么的,请前往搜狗百科-树

树链剖分,又名轻重路径剖分、树剖,是一种 看起来十分高大上实际很水的能让你代码强行增加180行的不那么容易爆炸(并不)的算法,本质上是将树转化为一系列重链轻边(这两个东西的定义后边会讲),然后用线段树(或一切支持区间修改和查询操作的数据结构,但其中线段树能维护的信息最广泛)进行存储。

树链剖分十分实用(前提是你线段树写的很熟练,不然满屏RE。。。),能将复杂的树上维护转化为简单相对不那么复杂的区间维护。

树链剖分的作用有:

  • 证明出题人是个毒瘤
  • 修改静态树上两点间最短路径上的所有点权(边权可以边转点解决)
  • 查询静态树上两点间最短路径上的点权和及最值(或任何你可以想到的满足区间可加性的信息)
  • 修改一个点及其子树上的所有点权
  • 查询一个点及其子树上的所有点权和及最值(其他信息同上)

树剖也能解决,但一般不用树剖解决的问题有:

  • 求LCA(60行和180行你选哪个)
  • 只维护树上两点间最短路径上的所有点权(树上差分就可以)
  • 只查询树上两点间最短路径上的点权和(依然是树上差分)

思路

首先给出几个定义:

  • 重儿子:一个节点的子树中节点数最多的子树的根(如果有多个可以取任意一个)
  • 重链:由重儿子连接形成的链
  • 轻边:树中不属于重链的其他边

树链剖分示意,其中点上的数是编号,加粗的边为重边:

5c24d0664c185.png

上面的图中,点1,2,3,4,5,6构成一条重链,点7,8,9,11,13构成一条重链,点12、14分别构成两条长度为1的重链(自己)

树链剖分的性质:

  • 树上的所有点属于且仅属于一条重路径
  • 设size[x]为x的子树大小,则如果(u,v)为轻边,size[u]<=size[u]/2(因为u已经有一个重儿子,而如果v的子树大小超过u的一半,则v应该是重儿子)
  • 因此,对于任何非根节点u,在u到根的路径上,轻边和重链最多有 $logn$条

实现

预处理

为了预处理树剖的操作,我们需要计算如下几个值:

1
2
3
4
5
6
7
8
9
对树中的每一个节点x
father[x]:x在树中的父亲
dep[x]:x的深度
size[x]:x的子树节点数
hson[x]:x的重儿子
top[x]:x所在重链的顶部节点(深度最小)
seg[x]:x在线段树中的位置(下标)
rev[x]:线段树中第x个位置对应的节点编号

我们需要两遍dfs来计算这些值,第一次DFS可以计算前四个值,第二次DFS可以计算后三个值。预处理代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
void dfs1(int u,int f) {
size[u]=1; //子树大小默认为1
dep[u]=dep[f]+1; //深度
father[u]=f; //记录父亲
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i]; //使用vector存图
if(v!=f)//排除父亲
{
dfs1(v,u);
size[u]+=size[v]; //累加子树大小
if(size[v]>size[hson[u]]) hson[u]=v; //如果v的子树大小比当前重儿子的大小大那么更新重儿子
}
}
}

void dfs2(int u,int f) {
if(hson[u]) //先走重儿子,使重儿子在线段树中的序号连续,这样才能用区间操作维护重链信息
{
seg[hson[u]]=++tot;//插入点
top[hson[u]]=top[u];//u和重儿子同属于一条重链
rev[tot]=hson[u]; //此时tot为当前点
dfs2(hson[u],u);
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i];
if(v!=f && v!=hson[u]) //排除父亲也不是重儿子
{
seg[v]=++tot;
top[v]=v; //轻儿子一定是重链的顶部节点
rev[tot]=v;
dfs2(v,u);
}
}
}
}

int main() //主函数
{
/*other codes*/
dfs1(root,0);
seg[root]=tot=1;
rev[1]=top[root]=root;
dfs2(root,0)
build(1,1,n);
/*other codes*/
}

操作

1.路径查询

给定两个点x,y,统计x到y最短路径上的信息:

  • 如果x、y属于一条重链(即top[x] $=$ top[y]),那么直接进行一次线段树的区间查询即可
  • 如果x、y属于两条重链(即top[x] $\ne$ top[y]),那么一定是由x走到 $LCA(x,y)$ 再走到y,此时
    • 首先找到top深度较大的点(因为LCA一定不可能在顶部节点深度较大的重链上)
    • 假设这个点是x,那x可以直接跳到father[top[x]],并在线段树上统计[seg[x]~seg[top[x]]]的信息(这会使x跳到一条离根更近的重链上)
    • 重复上面的操作直到top[x] $=$ top[y],此时用一次区间查询统计[x~y]的信息

代码(以统计和为例):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int qrange(int x,int y)
{
int ans=0;
while(top[x]!=top[y]) { //当x、y属于两条重链
if(dep[top[x]]<dep[top[y]]) //找到top深度较大的点
swap(x,y);
ans+=query(1,seg[top[x]],seg[x]); //区间查询,统计[seg[x]~seg[top[x]]]的信息
x=father[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans+=query(1,seg[x],seg[y]);//统计[x~y]的信息
return ans;
}

2.路径修改

给定两个点x,y,更新x到y最短路径上的信息:

方法同上,只不过将区间查询换成区间修改。
代码:

1
2
3
4
5
6
7
8
9
10
11
12
void crange(int x,int y,int k)
{
while(top[x]!=top[y]) { //当x、y属于两条重链
if(dep[top[x]]<dep[top[y]]) //找到top深度较大的点 swap(x,y);
swap(x,y);
update(1,seg[top[x]],seg[x],k); //更新[seg[x]~seg[top[x]]]的信息
x=father[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
update(1,seg[x],seg[y],k);//更新[x~y]的信息
}

3.子树查询

统计x及其子树上的信息:

这个更简单了,由于x的子树在线段树上是连续的,同时size[x]又储存了x的子树大小,因此直接用一次区间查询统计[x~x+size[x]-1]上的信息即可

代码:

1
2
3
4
5
int qson(int x)
{
return query(1,seg[x],seg[x]+size[x]-1);
}

3.子树修改

更新x及其子树上的信息:

方法同上,只不过将区间查询换成区间修改。
代码:

1
2
3
4
5
void cson(int x,int k)
{
update(1,seg[x],seg[x]+size[x]-1,k);
}


例题

文章作者: 1379号监听员
文章链接: https://listener1379.site/2019/【算法笔记】树链剖分/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 1379号监听站