隐藏
长链剖分学习总结 | Bill Yang's Blog
0%

长链剖分学习总结

长链剖分常用于优化一类特殊的动规,它可以在满足某些要求时,将$O(n)$的转移复杂度均摊为$O(1)$。
此外,长链剖分还有一些优秀的性质,但目前长链剖分在信息学竞赛中应用并不广泛。

定义

长链

长链的概念与重链类似。
点$x$的长链指从点$x$出发,到达其最深的后代所经过的路径。

重儿子

$x$所在的长链上的儿子称为重儿子。
称为长儿子总觉得有什么不对

长链剖分

长链剖分的概念与重链(树链)剖分类似。
通过树上存在的长链,将树剖分为若干条不相交的路径。

顶点

称树上一条长链深度最小的点为该长链的顶点。

性质

性质$1$

对树长链剖分后,树上所有长链的长度和为$O(n)$。

此性质显然成立。

性质$2$

任意一个点$x$的$k$级祖先$y$所在长链长度一定$\ge k$。

证明:

  1. 若$x,y$在同一条长链上:

    显然成立
  2. 若$x,y$不在同一条长链上:

    因为不在同一条链,所以别的子树一样深或更深,结论依然成立。

应用

由于长链剖分根据深度大小进行剖分,因此可以解决一些与深度有关的问题。

应用$1$:$O(n\log n)-O(1)$在线询问一个点的$k$级祖先

首先花费$O(n\log n)$的时间预处理出ST表。
接着对树进行长链剖分,记$Len(x)$为点$x$所在长链长度。
对于每一个长链的端点$x$,求出其$\sum\limits_{i=1}^{Len(x)}$级祖先与$\sum\limits_{i=1}^{Len(x)}$级重儿子。
因为性质$1$,预处理时空复杂度均为$O(n)$。
同时预处理出$1\rightarrow n$每个数二进制表示最高位的$1$,也就是$highbit$,时间复杂度$O(n)$。

对于每次询问$x$的$k$级祖先,首先利用ST表跳跃到$x$的$2^{highbit(k)}$级父亲$y$处,令$r=highbit(k)$,显然有$k-r\lt r$。
根据性质$2$,有$y$所在长链长度$\ge r\gt k-r$,因此有$y$所在的长链顶点预处理的表一定包含$x$的$k$级祖先。
因此可以做到$O(1)$回答询问。

例题

应用$2$:$O(n)$统计每个点子树中以深度为下标的可合并信息

这个应用的思想十分类似Dsu on tree
思想是当前结点直接继承重儿子的信息,轻儿子信息暴力统计。
因为长链剖分的特殊性,因此这个应用仅限于以深度为下标。
更一般的就只能使用Dsu on tree做到$O(n\log n)$的复杂度了。

更具体地:
若需求出点$x$的信息,首先从重儿子继承。
因为以深度为下标,因此只需要对数组进行移位即可。
后面我们会提到移位的实现方法。

接着,轻儿子的信息暴力合并到当前的信息中。

时间复杂度$O(n)$。
分析如下:
每个点$x$只会暴力统计其所有轻儿子的信息,而每个轻儿子的信息大小为该轻儿子所在长链长度。
而当递归到$x$的父节点$fa(x)$时,若$x$不是$fa(x)$的重儿子,则$fa(x)$会暴力统计大小为$x$长链长度的信息。
故,每个长链只会对转移的复杂度做一次大小为其长度的贡献。
因此根据性质$1$,总时间复杂度为$O(n)$。

移位的实现方法
本处仅提到一种实现方式,但方法不只有这一种。
用指针维护动规数组,在重儿子传递给父亲时将指针左移/右移一位。(左移还是右移根据转移方程决定)
而给其他轻儿子分配不相交的内存即可。

不难发现,这样实现的空间复杂度仍为$O(n)$。
特别注意,这样实现也有相应的缺点,即若动规的数组高于一维,那么数组是一次性的,不能在完成转移后查询中间过程的值。
原因是部分内存被共用掉了。

例题

参考资料

姥爷们赏瓶冰阔落吧~