专栏文章

浅谈树上轻重链剖分

ccritnos
算法·理论参与者 26已保存评论 33

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
33 条
当前快照
1 份
快照标识符
@mhz5tehw
此快照首次捕获于
2025/11/15 01:56
4 个月前
此快照最后确认于
2025/11/29 05:25
3 个月前
查看原文
（如果文章有什么错误请指出）
注意：本文非入门文章。请保证自己了解轻重链剖分，并能运用基础数据结构再进行阅读。
一些特别重要的常识：
  • 到根的路径被拆为若干个重链的前缀。
  • 轻子树大小和为 O(nlog⁡n)O(n\log n)。
一些记号：
  • (x,y)(x,y)：边。
  • v(x,y)v(x,y)：(x,y)(x,y) 的边权。
  • fafa：父亲。
  • dd：深度。
  • toptop：链顶。
  • x→yx\to y：路径。
  • dis(x,y)dis(x,y)：x→yx\to y 的长度。
  • lca(x,y)lca(x,y)：x,yx,y 的最近公共祖先。
题单。

一个没用的小知识

对每条重链单独均匀分块，路径上会有 O(n)O(\sqrt n) 个散块和整块。
从上至下第 ii 条链长度为 O(n2i)O(\dfrac n {2^i})，∑n2i=O(n)\sum \frac {\sqrt n} {2^i} = O(\sqrt n)。
一个简单的应用是链加链 rank 的平凡做法，对每条长为 xx 的重链按块长为 Θ(xlog⁡x)\Theta(\sqrt{x\log x}) 分块，容易计算得时间复杂度为 O(nnlog⁡n)O(n\sqrt{n\log n})。
看起来没用的原因是：除了常数的一些优势，看起来不比树分块。

长度为 kk 的树链数量

法一：
枚举一个端点 uu，利用轻重链剖分结构优化枚举 LCA。
从 uu 向上跳重链。设现在跳到点 xx，那么考虑 LCA 在 x→topxx\to top_x 上的贡献。
点 xx 特殊。lca(u,y)=xlca(u,y)=x 的点 yy 位于 xx 的除去包含 uu 的子树（就是跳上来的那个轻子树）。考虑到 xx 有 O(log⁡n)O(\log n) 个，对于这类，用 dfn 序扣除该子树即可。
（uu 点特殊，他的整个子树都需要被计入）
那么就是求被扣除一个子树的 xx 的 dfn 区间中 dy−dx=kd_y -d_x =k 的数量。扫描线即可。
对于 fax→topxfa_x \to top_x 上的点 pp，yy 位于其轻子树中。
考虑统计 dis(x,y)=dx+dy−2×dp=kdis(x,y)=d_x +d_y -2\times d_p=k 即 dy−2×dp=k−dxd_y -2\times d_p=k-d_x 的数量。
对于每个 pp 及其轻子树，dy−2×dpd_y -2\times d_p 为定值。
对每条重链进行扫描线即可。O(nlog⁡n)O(n\log n)。
关于这个扫描线是什么东西（与本文关系不大，可以了解）：
考虑这样一个问题：每次求区间 [l,r][l,r] 中某数出现次数。
拆成 [1,r]−[1,l−1][1,r]-[1,l-1]。
然后做从 11 到 nn 的扫描线。设现在扫到 xx。我们处理所有形如“[1,x][1,x] 中某数出现了多少次的询问”。
维护一个桶即可。
法二：
枚举每个点 xx 作为 LCA，合并子树答案。
轻子树的贡献可以直接遍历并维护一个桶（类似点分治），这个时间复杂度为 O(nlog⁡n)O(n\log n)。
对于重子树，我们递归处理下去。
设重儿子为 pp，递归处理这个儿子后桶保存了 pp 到其子树中每个点的路径信息。
加入 (x,p)(x,p) 后，桶中的数都加了 v(x,p)v(x,p)。tag 即可。
再枚举轻子树，计算出轻子树对重子树的答案。
最后将轻子树的贡献加入。这里就保存了 xx 到子树中每个点路径的信息。
所以是自洽的。O(nlog⁡n)O(n\log n)。
是不是特别眼熟？
这个就是“dsu on tree”，这也是为什么它也叫“静态链分治”的原因。
冷静一下，这个的本质就是对每条重链从链底到链顶做扫描线。

静态邻域交换半群

“邻域”的定义：给定 u,du,d，集合 {x∣dis(u,x)≤d}\{x|dis(u,x)\le d\} 形成的连通块。
交换半群：大概可以理解为，有交换律和结合律的抽象信息。
沿用上面的法一的思想：优化枚举祖先。
考虑点 xx：
对于 xx 的 dfn 区间中（扣除某子树）的 yy，dis(u,y)=du+dy−2×dx≤ddis(u,y) = d_u +d_y -2\times d_x\le d 即 dy≤d−du+2×dxd_y \le d-d_u +2\times d_x 的 yy 的信息并。
按深度排序后维护可持久化线段树（离线即可扫描线）维护 dfn，直接查询即可。O(log⁡2n)O(\log^2 n)。
考虑 fax→topxfa_x \to top_x：
同理，维护从重链顶到每个点路径上包含的轻子树信息。用可持久化线段树维护深度即可。O(log⁡2n)O(\log^2 n)。
值得一提的是，点分树也是可以做的。
不要认为点分树只能容斥。我们在每个点将其点分树子树中的点按照所属子树排列。扣除一个子树，即剩下前后缀。用可持久化线段树维护前后缀点深度即可。O(log⁡2n)O(\log^2 n)。
上面的是平凡方法。
考虑使用全局平衡二叉树，学名我忘了。不会的可以看一下：
如果我们对每条重链建立平衡二叉树结构，那么每个重链的前缀就可以在二叉树结构上搜索出来。
然而这并没有优化时间复杂度。
所以考虑给每个点加权。权为其子树大小减去重儿子子树大小。
然后建立带权平衡二叉树结构。理解一下，发现一定存在一个点满足将序列划分为两半，使得每一半的和均不超过总和的一半。
那么每个点在带权平衡二叉树和轻边上跳子树大小均翻倍。所以跳 O(log⁡n)O(\log n) 次。
考虑 xx 处的查询，显然是 xx 到重链链底上面挂的轻子树，减去跳上来的轻子树。这个不能容斥，为了减掉这个轻子树，对每个结点挂的轻子树建立哈夫曼树。fax→topxfa_x\to top_x 就是上面挂的轻子树。全局平衡二叉树结构都可以直接分解。
对每个节点维护前缀和即可，时间复杂度 O(log⁡n)O(\log n)。注意现在不能简单地直接用每个点在树上的深度了。
点分树当然也可以做到 O(log⁡n)O(\log n)。为了减去某棵子树，同样可以对子树建哈夫曼树。所以也可以用边分树。
上面的仍然不是最优时间复杂度。[NOI2022] 树上邻域数点，使用 rake/compress 操作，O(nlog⁡n)−O(1)O(n\log n)-O(1) 处理。一个简单的解法是，设计树分块满足每块是 cluster 并且直径有限制。按块大小为 2k,k∈[0,log⁡n)2^k,k\in[0,\log n) 分块，每次询问放到较小的最接近的块大小上处理，这样每次可以分解为一个整块+两个散块。对散块用长链剖分预处理即可。

后缀数据结构求区间 border

通过 SAM 或者后缀树对字符串题进行转化，LCA 经常出现。轻重链剖分会显得很重要。
设 border 的起点为 ii，那么 r−i+1≤lcp(l,i)r-i+1\le lcp(l,i)。
建出反串的 SAM，设点 ii 在 SAM 上的位置为 rkirk_i，显然 r−i+1≤lenlca(rkl,rki)r-i+1\le len_{lca(rk_l,rk_i)}。
扫描线，扫到 ll 时加入询问，扫到 r+1r+1 时删除该询问。
那么对于每个 ii，我们取出所有的满足这个 ii 是询问区间 border 的询问即可。
从 rkirk_i 向上跳重链（优化枚举祖先），假设现在跳到了点 uu，考虑该重链前缀的贡献。
  1. lca(rkl,rki)=ulca(rk_l,rk_i)=u
显然这类 rklrk_l 几乎在点 uu 的子树内。
断言这个“几乎”是没有影响的，因为这类点之前算过了。这个显然没有影响。
现在 i,lcai,lca 是确定的，那么移项得 r≤lenlca(rkl,rki)+i−1r\le len_{lca(rk_l,rk_i)}+i-1。
那么每次取出子树中的最小值判断即可。
  1. lca(rkl,rki)=vlca(rk_l,rk_i)=v，vv 为 fau→topufa_u \to top_u 上的点。
这类 rklrk_l 在 vv 的轻子树内或 rkl=vrk_l=v。
因为 rklrk_l 显然不在 vv 的重子树内，否则之前就算过了。
那么有 r−lenlca(rkl,rki)+1≤ir-len_{lca(rk_l,rk_i)}+1\le i。
在插入询问的时候枚举包含其的轻子树，显然是 O(log⁡n)O(\log n) 个。
同理，每次取出链中的最小值判断即可。
那么上面的两类引导我们设计这样一个数据结构，维护序列（上面的用 dfn 拍平），支持在一个位置插入（相当于每个位置是个可重集？），求区间最小元组，删除一个位置的最小值。
小孩都会，每个位置维护个堆，用线段树维护区间最小值即可。
时间复杂度为 O(nlog⁡2n)O(n\log^2 n)。

CF1098F Ж-function

题目：给出一个字符串，每次给区间 [l,r][l,r]，求所有起点在 [l,r][l,r] 中的后缀和 [l,r][l,r] 的 LCP 长度之和。
通过简单的 SAM 转化，我们得到这样一个问题：
一棵树，点带权 vv；存在映射关系 rkrk（从 id∈[1,n]id \in [1,n] 映射到树上的节点）。每次给 l,r,ul,r,u，求
∑i=lrmin⁡(vlca(u,rki),r−i+1)\sum _{i=l}^r \min (v_{lca(u,rk_i)},r-i+1)
如果没有 min⁡\min 就是经典问题。考虑差分后扫描线。
从 uu 向上跳重链。考虑链 (x,topx)(x,top_x)。
对于 xx：
  1. vx≤r−i+1v_x \le r-i+1 即 i≤r−vx+1i \le r-v_x +1。
即子树扣掉了某子树中满足条件的 ii 的数量。
  1. vx>r−i+1v_x > r-i+1
同理。求满足条件的 ii 和。
对于 p∈fax→topxp\in fa_x \to top_x：
vp≤r−i+1v_p\le r-i+1 即 vp+i−1≤rv_p +i-1 \le r。
上面两个东西都是三维偏序模型（因为扫描线要加点）。一般来说，轻重链剖分会造成 O(nlog⁡n)O(n\log n) 次查询。
所以时间复杂度为 O(nlog⁡3n)O(n\log ^3 n)。
考虑优化。使用全局平衡二叉树。
对于 xx：
我们发现查询的本质上是他的到链底的点的轻子树和他到链底上的点减去他的某个子树。这个也是可以在带权平衡二叉树上搜索出来的。
那么在加点的时候就对所有轻子树包含他的 O(log⁡n)O(\log n) 个点加贡献。在全局平衡二叉树上跳，用平衡树维护即可。
对于 fax→topxfa_x \to top_x：
变成了前缀而已。是同理的。
时间复杂度 O(nlog⁡2n)O(n\log ^2 n)。

stcm

题目：给出一棵树，你可以对一个集合进行三种操作：加点/撤回上次加点/表示某点的子树补为当前集合。要求表示出每个点的子树补，操作次数限制 O(nlog⁡n)O(n\log n)。
如果我们得到了一条重链顶端的子树补，考虑处理整条链并递归下去。
处理链上的点是简单的。考虑由上自下处理，处理完一个点就加入其轻子树和本身。这里是 O(nlog⁡n)O(n\log n)。
考虑如何推到其轻儿子上。如果可以，那么算法就自洽了。
不妨考虑树为菊花的情况。
对轻儿子进行分治。每次标记左/右一半的轻儿子，然后处理右/左一半的轻儿子。这样是 O(nlog⁡n)O(n\log n) 的。
回到一般的情况，是类似的。但如果平衡地划分是 O(nlog⁡2n)O(n\log^ 2 n) 的。
类似全局平衡二叉树，带权二分即可。O(nlog⁡n)O(n\log n)。
有一个常数更优的解决方案。因为这里没有提取链上区间的要求所以顺序无关。这类问题的最优树结构是哈夫曼树。用哈夫曼树代替带权二分会得到更优秀的常数。
小练习：

评论

共 33 条评论，欢迎与作者交流。

正在加载评论...