【算法笔记】树链剖分
*强烈建议在阅读本文之前已经掌握前置知识 线段树,如果你没有,请先阅读这篇文章*
不知道树是什么的,请前往搜狗百科-树
树链剖分,又名轻重路径剖分、树剖,是一种 看起来十分高大上实际很水的能让你代码强行增加180行的不那么容易爆炸(并不)的算法,本质上是将树转化为一系列重链和轻边(这两个东西的定义后边会讲),然后用线段树(或一切支持区间修改和查询操作的数据结构,但其中线段树能维护的信息最广泛)进行存储。
树链剖分十分实用(前提是你线段树写的很熟练,不然满屏RE。。。),能将复杂的树上维护转化为简单相对不那么复杂的区间维护。
树链剖分的作用有:
证明出题人是个毒瘤- 修改静态树上两点间最短路径上的所有点权(边权可以边转点解决)
- 查询静态树上两点间最短路径上的点权和及最值(或任何你可以想到的满足区间可加性的信息)
- 修改一个点及其子树上的所有点权
- 查询一个点及其子树上的所有点权和及最值(其他信息同上)
树剖也能解决,但一般不用树剖解决的问题有:
- 求LCA(60行和180行你选哪个)
- 只维护树上两点间最短路径上的所有点权(树上差分就可以)
- 只查询树上两点间最短路径上的点权和(依然是树上差分)
思路
首先给出几个定义:
- 重儿子:一个节点的子树中节点数最多的子树的根(如果有多个可以取任意一个)
- 重链:由重儿子连接形成的链
- 轻边:树中不属于重链的其他边
树链剖分示意,其中点上的数是编号,加粗的边为重边:
上面的图中,点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 | 对树中的每一个节点x |
我们需要两遍dfs来计算这些值,第一次DFS可以计算前四个值,第二次DFS可以计算后三个值。预处理代码:
1 | void dfs1(int u,int f) { |
操作
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 | int qrange(int x,int y) |
2.路径修改
给定两个点x,y,更新x到y最短路径上的信息:
方法同上,只不过将区间查询换成区间修改。
代码:
1 | void crange(int x,int y,int k) |
3.子树查询
统计x及其子树上的信息:
这个更简单了,由于x的子树在线段树上是连续的,同时size[x]又储存了x的子树大小,因此直接用一次区间查询统计[x~x+size[x]-1]上的信息即可
代码:
1 | int qson(int x) |
3.子树修改
更新x及其子树上的信息:
方法同上,只不过将区间查询换成区间修改。
代码:
1 | void cson(int x,int k) |
例题
- P3384 【模板】树链剖分(模板题)
- P2146 [NOI2015]软件包管理器(用0/1来维护)
- P3401 洛谷树(边转点)