树链剖分

AisDaeun 16 2023-11-14

树链剖分是什么?

树链剖分是一种高效解决树上问题的算法,可以解决如LCA查询(比倍增法常数低)、树上区间查询(修改)、子树查询(修改)等问题。他的基本思想是利用启发式合并的思想和DFS序的连续性,把树形结构转化为序列,把树上问题转化为RMQ问题。

如何进行树链剖分?

树链剖分主要有两种形式:重链剖分和长链剖分。一般而言,重链剖分的效果更佳。

在图论中,“重”这个字主要指的就是子树大小。例如:一个节点是树的重心,当且仅当删去它后剩余的最大子树最小。

在一颗有根树中,我们定义:

一个节点的所有儿子中,子树最大的儿子称为该节点的重儿子,其他儿子称为该节点的轻儿子

连接重儿子的边叫做重边,连接轻儿子的边叫做轻边

由重边组成的链叫做重链

显然,两个节点之间要么由重边连接,要么由轻边连接。

树链剖分的过程

主要分为两个预处理过程:

dfs1