基于线段树的单 log 树链剖分

hanbingqigu · 2026-07-26 18:55:50 · 算法·理论

基于线段树的单 log 树链剖分

太长不看版

仅需对普通的树剖做以下两个优化：

每条重链单独开一棵线段树。
定义每个节点的权值 w(x) = \operatorname {siz}(x) - \operatorname {siz}(\operatorname {hson}(x))。在建线段树时，二分区间的策略改为选取最佳的中点使得左右区间权值和尽可能相等。具体的，设当前区间为 [L, R]，选取第一个 x 使得 \displaystyle \sum_{i=L}^x w(\operatorname{rnk}(i)) \ge \frac 1 2\sum_{i=L}^R w(\operatorname{rnk}(i))，若 x = R 则强制令 x = R - 1，将 [L, R] 划分为 [L, x] 和 [x + 1, R]。

通过以上优化，可以证明单次路径操作的复杂度将优化为 O(\log n)。

复杂度证明

先抽象这棵线段树的结构。给每个叶子赋予一个权值 w(x)（w(x) \ge 1），定义非叶子节点的权值为区间权值总和，并且按照刚才的策略划分区间。

设根节点的权值为 W。

首先证明一个较为显然的引理：

引理

从根向下走到叶子，每走至多 O(1) 步当前节点的权值将减半。

证明

设当前节点代表 [L, R]，权值和为 S。

考虑策略的本质是找到第一个位置使得前缀和大于总和的一半。参考下图：

走右儿子

如果当前的 x 触发了 x = R 强制将 x = R - 1，那么右儿子是一个叶子。否则走到右儿子权值一定减半。

连续走两次左儿子

一定走到一个被 [L, x-1] 包含的区间，权值和一定减半。

连续走 2 步要么走到了一个叶子，要么一定包含一次走右儿子或者连续走两次左儿子，因此当前节点权值一定减半。\blacksquare

于是可以得到如下推论：

推论 1

树高为 O(\log W)，因此单次区间操作复杂度为 O(\log W)。

推论 2

从根节点走到叶子 x 需要的步数为 O(\log \dfrac W {w(x)})。

回到原问题。每个节点的权值定义为所有轻儿子子树大小之和加上自己本身。一个重链的权值和就是链顶的子树大小，因此每棵线段树满足 W = \operatorname {siz}(\mathit{top})。

建树

建一棵长度为 k 的线段树，如果每层找分割点直接暴力枚举，那么每层总次数为 k，总共 O(\log W)=O(\log n) 层，复杂度 O(k \log n)。由于 \sum k = n，建出所有线段树的总复杂度为 O(n \log n)，已经够用。

可以预处理前缀和，找分割点时二分找，复杂度有点难分析，有大佬会的教我。（AI 说最坏仍是 O(n \log n)，仅有常数优化作用）

路径操作

现在考虑一次路径操作（以查询为例，修改同理）。一次路径查询在重链上的查询状况分为两种：

查询重链的某一段区间
查询重链的某一个节点到链顶这一段区间。

情况 1 仅当两个点跳到同一条重链上才会出现，认为仅有 O(1) 次，查询总复杂度 O(\log n)（推论 1）。下面主要分析情况 2。

情况 2 在线段树上对应的是查询一个前缀区间，设查询的是 [1,x] 这个前缀，那么查询的复杂度等于从根走到叶子 x 所需的步数（前缀查询每次一定只递归单边，递归另一边时将会直接返回），为 O(\log \dfrac W {w(x)})（推论 2）。

不妨只考虑从起点走到一个祖先的情况。查询的时候一定由若干形如“从一个链顶跳到另一个链顶”的过程组成，如下：

从 x 跳到 x' 时，需要在线段树上查询 [\operatorname{dfn}(x'), \operatorname{dfn}(y)] 这一段（注意由于每条重链线段树单独开，因此这是一个前缀），复杂度为 O(\log \dfrac W {w(y)})。而 W=\operatorname{siz}(x')，又根据定义可知 w(y) \ge \operatorname{siz}(x)，因此 \dfrac W {w(y)} \le \dfrac {\operatorname{siz}(x')} {\operatorname{siz}(x)} ，复杂度可以写作 O(\log \dfrac {\operatorname{siz}(x')} {\operatorname{siz}(x)})。

接下来考虑整体的过程，不妨把每次到达的链顶列出来，记作 x_1,x_2,\dots,x_k，那么在线段树上查询耗费的总时间复杂度为：

\begin{aligned} \text{total} &=\sum_{i=1}^{k-1} O(\log \dfrac {\operatorname{siz}(x_{i+1})} {\operatorname{siz}(x_i)}) \\ &= O(\log \left( \dfrac {\operatorname{siz}(x_2)} {\operatorname{siz}(x_1)} \cdot \dfrac {\operatorname{siz}(x_3)} {\operatorname{siz}(x_2)} \cdots \dfrac {\operatorname{siz}(x_k)} {\operatorname{siz}(x_{k-1})} \right)) \\ &= O(\log \dfrac {\operatorname{siz}(x_k)} {\operatorname{siz}(x_1)}) \end{aligned}

显然 \operatorname{siz}(x_k) \le n，\operatorname{siz}(x_1) \ge 1，因此 \dfrac {\operatorname{siz}(x_k)} {\operatorname{siz}(x_1)} \le n。

综上所述，在线段树上查询耗费的总时间复杂度为 O(\log n)。

另外，跳轻边的次数为 O(\log n)，二者为相加关系。

综合以上所有分析，可以得到单次操作的时间复杂度为 O(\log n)。\blacksquare

实现与应用

对于常规的路径操作，无论是修改还是查询都符合上述复杂度分析，并且代码难度不大（~~毕竟线段树还是太轮椅了~~）。核心为 build 函数：

void build(int l, int r, int& p) {
    if (!p) p = ++tot;
    if (l == r) return;  // do something if need
    int S = 0, sum = 0, mid;
    for (int i = l; i <= r; i++) S += w[rnk[i]];
    for (mid = l; mid < r; mid++) {
        sum += w[rnk[mid]];
        if (sum * 2 >= S) break;
    }
    if (mid == r) mid--;
    md[p] = mid;
    build(l, mid, ls[p]);
    build(mid + 1, r, rs[p]);
    // push up...
}

然后把所有的 mid 替换为 md[p] 即可。查询和修改操作与之前一致。

另外在剖分时当走到叶子（重儿子不存在）记一下链底的 dfn 并且建树即可。注意要将线段树操作递归入口的左端点和右端点改为这条链的起始和终止 dfn。

这样就可以通过一些卡树剖的毒瘤题了，比如 P4751：

普通树剖：无法通过。
单 log 树剖：AC。

关于“全局平衡二叉树”

实际上，此树剖等价于建了一棵基于 Leafy Tree 的全局平衡二叉树，跳轻边和在线段树向下走分别等价于在全局平衡二叉树上跳轻边和跳重边。

因此子树操作也是可做的，需要标记永久化，参考全局平衡二叉树对子树的处理即可，交给读者思考。

相较于全局平衡二叉树，此做法无需重构原树形态，完全基于普通树剖，易于理解、实现简单，并且无需像全局平衡二叉树一样先找到路径再 push down，作者认为具有一定的优势。

碎碎念

某一天，大佬 wzl 提到线段树可以给节点赋权（如询问次数），调整树的形态以做到常数优化，复杂度不变，当时认为没啥用。

昨天看到了全局平衡二叉树，正在疑惑为什么要选取这样一个奇怪的权重，突然想到可以在普通树剖的线段树上应用这个权重！经过一个晚上与大佬 deepseek 和大佬 qss 的交流，终于完成了复杂度的证明并确认了正确性。感谢。

插句题外话，在与 deepseek 交流的过程中发现了很多有趣的内容：

d 老师说话真的很有意思。

另外，我在网上还没有看到有关这个算法的相关资料和详细的复杂度证明，独立地探索并且发现了新的东西时，那种激动和兴奋真是难以言表，~~导致晚上两点半还没睡着觉~~，也许这就是 OI 最大的魅力吧！不过如果有相关资料请踢我。

如果发现任何问题，请立即私信作者 hanbingqigu，感谢不尽！

本文完全由真人创作。证明部分与 AI 协助完成。使用了 AI 勘误。

finished on 2026/7/26