RainAir
My OI Blog
RainAir
树链剖分学习笔记

树链剖分是一种树路径信息维护算法。

把整棵树划分成许多条,使每个节点都在唯一的链上,对每一条链维护一棵线段树,把在树上的操作转移到线段树上。

ž将一棵树划分成若干条链,用数据结构去维护每条链,保证每个点在且仅在一条链上,通过数据结构维护这些链的信息,复杂度为$ O(logN) $

接下来我们以一道例题为例。

P3384-树链剖分

如题,已知一棵包含 $ N $ 个结点的树(连通且无环),每个节点上包含一个数值,需要支持以下操作:

  • 操作1: 格式: $1\ x\ y\ z $ 表示将树从x到y结点最短路径上所有节点的值都加上 $ z $
  • 操作2: 格式: $2\ x\ y $ 表示求树从x到y结点最短路径上所有节点的值之和
  • 操作3: 格式: $3\ x\ z $表示将以x为根节点的子树内所有节点值都加上 $ z $
  • 操作4: 格式: $4\ x\ $表示求以x为根节点的子树内所有节点值之和

有 $ M $ 次操作,其中 $N \leq 10^5,M \leq 10^5$

树链剖分

介绍

我们先明确一下概念:

  • 重儿子:在一个点 $ u $ 的儿子中,拥有最大的 $size$ 值的点 ,就叫做是点 $ u $ 的重儿子。
  • 轻儿子:点 $ u $ 的儿子中除了 $ u $ 的重儿子外的所有儿子。
  • 重边:点 $ u $ 于其重儿子的连边。
  • 轻边:点 $ u $ 与其轻儿子的连边。
  • 重链:仅由重边构成的路径

那么我们不难发现,树链剖分有一些保证复杂度的优秀的性质。

  • 性质1:如果 $ v $ 是 $ u $ 的轻儿子,那么 $ size_v \leq \frac{size_u}{2} $ 。
  • 性质2:任意点 $ u $ 到根的路径上轻边,重链条数都不大于 $ log_2n $ 。

定义

树链剖分需要定义三种结构体,树的节点,树的边,链。

代码定义如下:

剖分过程

这个过程是划分轻重链的过程。

我们用两遍 dfs 来实现。

对于第一遍 dfs,求出每个节点的 $ size,depth,fa,maxchild $ ,对于第二遍 dfs,求出 $ dfn,chain $ (定义见上文)

剖分过程代码如下:

维护链上信息

我们使用线段树来维护信息,每个线段树节点的编号是树上节点所对应的 $ dfn $ 值。

线段树(或其他数据结构)的定义要随着题目的改变而改变。

查询&修改

对于树链剖分后的查询和修改操作,只需要考虑如何转换到线段树上的区间修改操作即可。

我们以操作 $ 1 $ 和 $ 2 $ 为例,设 $ u $ 的深度更深,我们先让 $ u $ 跳到 $ v $ 所在的链上,途中进行 修改/查询 ,最后对 $ u $ 和 $ v $ 剩下的区域进行 修改/查询 即可。

操作二留给读者作为思考题,要考虑修改的内容和 $ dfn $ 序的关系,进而才能确定与线段树修改的关系。

最近公共祖先

树剖求最近公共祖先,也是先让 $ u $ 跳到 $ v $ 所在的链上,然后返回 $ depth $ 小的点。

全部代码

思考题答案:我们考虑修改一个以 $ v $ 为根子树的时候,最小的 $ dfn $ 的节点是 $ v $,$ dfn $ 最大值就是 $ dfn_v + size_v – 1 $。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/109
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

树链剖分学习笔记
树链剖分是一种树路径信息维护算法。 把整棵树划分成许多条链,使每个节点都在唯一的链上,对每一条链维护一棵线段树,把在树上的操作转移到线段树上。 ž将一棵树划分成若干条链,用数…
扫描二维码继续阅读
2018-06-18
标签
近期评论