算法详解——树链剖分

发布于 2017-05-05  535 次阅读


 

Warning


由于本博客作者实在是太弱啦,本篇文章可能存在大量的错误,漏洞,不规范,不合法之处。若您发现本文章所存在的任何问题,请您尽快在评论区指出,十分感谢!

另外,本文随意转载,但请注明出处。

前置


在阅读本篇文章之前,你至少应该了解并初步掌握以下知识:

同时若你了解以下知识,它们会帮助你理解:

  • 树形 dp
  • dfs 序

问题


我们有时会遇到这样的问题:

给定一棵节点数为 n 的树,对于每个节点,具有一个点权 w[i],有 m 次操作:

  • change u t 将节点 u 的点权设为 t
  • qmax u v    询问 u 到 v 路径上的最大点权
  • qsum u v    询问 u 到 v 路径上的点权和

n≤30000   q≤200000  保证任意时刻 w[i] 在 [-30000,30000]...

思考


看到问题,我们一定会发现,这和序列操作的问题十分相似... 所以我们考虑用线段树维护点权来解决问题,我们需要构造一种映射关系,使得树上的点与线段树维护的一维序列满足某种对应关系。

暴力编号的想法很明显的,然而不足之处也是很显然的... 这样更新一个点权是\(O(log_2^{n})\) 的复杂度,然而,当我们查询某个路径的时候... 我们需要枚举 u->v 间的所有节点,这样做的复杂度是树的直径... 退化为了暴力的\(O(n)\) 复杂度... 所以我们需要考虑一种具有良好性质的映射关系,使得复杂度能在各种情况下都得到保证...

我们考虑对某些点一起处理,将一棵树剖分成若干条链,这种剖分方案是满足复杂度要求的,对于每一条链,用数据结构去维护它。

这就是树链剖分

定义


在介绍树链剖分前,你需要了解以下概念~

  • 重儿子:对于节点 x 而言,它的重儿子 son[x] 即它的儿子中子树最大的节点
  • 轻儿子:对于节点 x 而言,它的非重儿子均为轻儿子
  • 重边:对于节点 x 而言,它与它的重儿子 son[x] 间的边即为重边
  • 轻边:非重边均为轻边
  • 重链:连续相连重边所构成的链即为重链

请熟悉以上概念,它们将在下面的讲解中被反复提及

树链剖分


我们通过以上定义划分这棵树后,显然,一条从 u 到 v 的路径是由一些重链和一些轻边组成的,对于以上划分方式,有一个很良好的性质:

  • 对于一条从节点 x 到根节点的路径,最多有\(log_2^{n}\) 条重链和\(log_2^{n}\) 轻边

 


一个非常弱的准退役OIER