树链剖分算法解析

本文部分内容参考自 这篇博客 (写的很好 Orz ,建议大家也去看一下)

树链剖分是什么?用来做什么?

有一棵树,求解以下问题:
1. 将从 x 到 y 的路径上的每个结点权值增加 z
2. 求从 x 到 y 的路径上的每个结点的权值和/权值最大值/权值最小值

对于问题 1,我们可以用树上差分来求解。

对于问题 2,我们可以用类似前缀和的方法,预处理出每个点及其上面的点的权值和,利用 LCA ,减一减就得到了答案。

单独求解每个问题都很简单,这两种问题结合起来,上面的方法就不理想了。

而树链剖分可以巧妙地解决这一类问题。

一种对树链剖分直白的解释

树链剖分其实是把树的结点编号重组了,原先的每个结点都被分配了一个新的编号。

重新编号有什么好处?重新编号后的树,存在有若干条特殊的链,每条链上的新编号都是连续的。

这就方便了我们使用线段树/树状数组等数据结构来快速对这些链上的结点进行求和/求极值/修改。

注意:原树的每一个结点都被放入线段树中了,只是有一些树上的链对应线段树里的一些连续区间。

如图,重组编号后,使用这些编号为下标建立一棵线段树,那么 1-2-3 这条链的极值/和就可以很快求出了。

一些基本的概念

在上文中我们已经了解,经过这种重组以后的树存在一些新编号连续的链,它们就叫做重链,而重链中的每一条边就叫做重边

与之相对,其余的边就叫做轻边,它们组成的链就叫轻链

你只需要记住重链是一些特殊的链即可。

那么如何划分重链呢?很简单。

对于一个结点,它的儿子分为轻儿子重儿子。重儿子只有一个,其余的都是轻儿子。

如果一个子结点下面的结点很多(只要是子树中的都算),它的兄弟都比不上它,那它就是重儿子了。其余的都是轻儿子。

(如果每个儿子子树结点个数一样怎么办?当然是随便选一个)

(如果只有一个儿子怎么办?没有人竞争了,当然就是重儿子了)

例如下面这张图,结点 2 有 5 个子树结点,而结点 3 只有 3 个子树结点,结点 2 完胜,所以结点 2 就是结点 1 的重儿子。

注意:树根是重儿子(虽然它没有父亲,就叫它重节点吧)

前面提到的重链同时也是重儿子组成的链,轻链当然就是轻儿子组成的链了。

小结一下

名字(概念) 解释
重儿子/重结点 一个子树结点数量比它的每一个兄弟都多的结点,当然树根也是
轻儿子/轻结点 其余的结点(一个父结点除了重儿子以外的儿子)
重链 重结点/重儿子组成的链
轻链 轻结点/轻儿子组成的链
重边 重链里的边
轻边 轻链里的边

和下文相关的一道例题

在开始讲代码之前,先看一道例题,下文围绕它展开。

洛谷P2590 – [ZJOI2008] 树的统计

下文代码的读入输出规范、数据范围等以这道例题为准。

预处理

预处理分为两次,不过很简单

第一次预处理

我们需要知道一个结点之下有几个子树结点,于是我们使用 size[i] 来表示结点 i 有几个子树节点。

我们需要知道结点的深度(后面有用),所以我们使用 d[i] 来表示结点 i 的深度(树根深度为 1)。

我们还需要知道每个结点的父亲结点(还是后面有用),所以我们使用 f[i] 来表示结点 i 的父亲结点。

我们必须要知道每个结点的重儿子,所以我们使用 son[i] 来表示结点 i 的重儿子。

我们当然可以用一遍 dfs 就预处理求出这几个数组。

然后我们这么调用它: dfs1(root,root,1)

对调用的解释:从根节点开始 dfs,根节点的父节点是其本身,深度为1 (在本题中,根节点为编号为 1 的结点 ,所以本题中 root 为 1)

第二次预处理

等等,好像还少点什么。

光有这个没用啊,我们不是要重组编号吗。

我们需要知道一条重链的顶端结点编号,那么就用 top[i] 表示结点 i 所在重链的顶端结点编号。(如果它在轻链上,那就自成一链,顶端是它本身)

要知道顶端编号怎么办?我们肯定要 dfs ,dfs 肯定以重链为标准,那就顺便记录一下当前结点的 dfs 序,用 id[i] 来表示,这同时也是当前这个结点重新分配编号后的新编号。

既然都有新编号了,我们就干脆把结点按照新编号排成一个新数组,用 rk[i] 表示重排后的第 i 个点在重排前的编号。(不好理解?没关系,看代码就明白了)

这次的 dfs 和第一次有一些不一样,传的两个参数分别是 当前结点的编号 和 当前结点所在重链顶端结点的编号

dfs 之前,需要知道:一个结点如果是重儿子,那么它是一条重链中的一员;如果是轻儿子,那么它是一条重链的顶端。

我们这么调用它: dfs2(root,root)

本文使用的线段树模板

下面说明一下本文使用的线段树模板操作,以免混淆

build()  初始化线段树

updata(l,r,root,x,ans)  更新单点,将 x 点的值设为 ans

find_sum(maxl,maxr,root,l,r)  返回区间 [l,r] 中的总和

find_max(maxl,maxr,root,l,r)  返回区间 [l,r] 中的最大值

最后最后的预处理

我们得到了 rk 数组,现在只要开一棵线段树,build一下就好了。

↑ 你应该会的代码(线段树模板还有一部分就省略了)

那求上面那些其他的数组没用了?当然有。

下面我们进入正题。

树链剖分的操作

LCA

用树链剖分求 LCA 速度很快,也很简洁。

步骤

现在我们想求结点 x 和 y 的 LCA。

  1. 判断 top[x] 是否等于 top[y]
  2. 如果不等于,如果 d[x]>d[y],那么 x=f[top[x]] ,否则 y=f[top[y]] (更新深的结点)
  3. 如果 top[x] 还是不等于 top[y],跳回第一步
  4. 返回深度浅的结点的坐标(即 return d[x]>d[y]?y:x)

代码

两点之间求和/极值

做法

我们基于 LCA 的代码,修改一些地方,加入统计即可

求最大值

求最小值

同上,只是把 max 改成 min,注意线段树也要修改

求和

同上,只是改成累加

单点修改

很简单,直接上代码

两点之间权值修改

需要支持区间修改的线段树,只要把之前求 max 代码的更新过程改成修改过程就好了。

这里的代码是 洛谷 P3384 的 AC 代码,标准也和这道题一样

 

模板题代码

开头提到的那道题的 AC 代码

暂无评论

发送评论


				
上一篇
下一篇