斜二倍增 #超清大图

· · 算法·理论

老年人来感受 2025 年的科技浪潮了！

"斜二倍增"想要说什么？

我认为整个算法始于这个观察：

当我们有一个支持 push_back 和区间查询的向量时，线段树给我们 O(n) 的空间复杂度。（push_back 部分实际上并不重要 - 我们可以预分配一个足够大的线段树。）

但有趣的是：如果我们把这个向量看作树路径，那么 push_back 变成了添加叶子。突然间，传统的二进制提升（"树上倍增"）膨胀到 O(n \log n) 空间。 我们哪里做错了？

更仔细地看二进制提升结构，我认为它基本上只是应用于数组的"稀疏表"。这就是为什么一些论文称之为 "st-tree"，据我所知。 真正的问题是：我们如何将那种优雅的线段树带到树上？

        *
       / \
      *   *            ^
     /     \           |
....*.......*....      |
   /         \         |
  *           * <-- u  v
 /             \
*               *

关键洞察是：看图。我们在其中点（虚线）处切割树。对于节点 u，我们不需要存储 u 和其第 2 个祖先之间的信息，因为这个范围在我们的线段树中不存在。用树的语言来说，它穿过了虚线。

从线段树得到启发

要实现这个想法，我们先来看看线段树中每个右端点对应的区间长度：

              8
          4   4
        2 2 2 2 2 2
       111111111111
-------------------
index  123456789012
lowbit 010201030102

规律很明显：对于右端点 r，对应的区间长度是 2^0, 2^1, \dots, 2^{\text{lowbit}(r)}。

那么在树上呢，对于一个深度为 \text{depth}(u) 的节点 u，我们只需要存储长度为 2^0, \dots, 2^{\text{lowbit}(\text{depth}(u))} 的跳跃。

但是等一下...

看起来我们搞定了？O(n) 空间，每次加元素 O(1) 时间... 哎不对，这只是对一条路径有效！

考虑这棵树：

      *
      |
      *
      .
      .
      *
    / | \  ....
   *  *  * .... (最下面有很多叶子)

你看，最下面突然可以有很多叶子节点，每个叶子都要存 O(\log n) 个跳跃！这下空间又爆了...

一个巧妙的想法 - 斜二进制

这引导我去考虑一个"斜着"的线段树结构：

       (------------------------------)
       (-------------)(--------------)
       (-----)(-----) (-----)(-----)
       (-)(-) (-)(-)  (-)(-) (-)(-)
       ** **  ** **   ** **  ** **
--------------------------------------
                1111111111222222222233
index  1234567890123456789012345678901

这里的美妙之处是：对于每个右端点 r，只有 1 个区间与之相关联！我们记作 (r - L(r), r]。我们可以观察到存在 k \in \mathbb{N}^+ 使得 L(r) = 2^k - 1。

现在还不清楚如何高效地决定 L(r)，所以让我们暂时假设它是给定的。首先，让我们看看如何建树和如何查询。

如何建树：下面我们将使用"节点"而不是"右端点"。对于节点 u，它的和 \operatorname{sum}(u)（存储的跳跃的和）可以计算为：

\operatorname{sum}(u) = \operatorname{sum}(w) + \operatorname{sum}(v) + x_u.

如图所示：

     u
     |
     v
(-----)
(-)(-)
 ^  ^
 |  |
 w  v

从这个更新，我们也知道如何确定 L(u)：

如何查询：要查询 (r - x, r]，有两种情况：

至此，我们终于得到了一个 O(n) 空间和 O(1) 更新的结构（O(\log n) 查询）。

附注：我之前有过一个非常类似的困惑 - LCT 在 O(\log n) 时间内解决树路径查询，即使有形状变化，而轻重链分解即使对于静态树也总是需要 O(\log^2 n)。这让我想知道它们之间是否有更深的联系。而现在我们知道，还有"全局平衡二叉树"。（有趣的是，这个想法已经在杨哲的 2008 年集训队作业《QTREE 解法研究》中有详细记录，该文章向中国竞技编程社区介绍了 HLD。）