专栏文章

斜二倍增 #超清大图

fftiasch
算法·理论参与者 8已保存评论 7

文章操作

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

当前评论
7 条
当前快照
1 份
快照标识符
@mi4d8upd
此快照首次捕获于
2025/11/18 17:23
3 个月前
此快照最后确认于
2025/12/01 21:05
3 个月前
查看原文
老年人来感受 2025 年的科技浪潮了！

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

我认为整个算法始于这个观察：
当我们有一个支持 push_back 和区间查询的向量时，线段树给我们 O(n)O(n) 的空间复杂度。（push_back 部分实际上并不重要 - 我们可以预分配一个足够大的线段树。）
但有趣的是：如果我们把这个向量看作树路径，那么 push_back 变成了添加叶子。突然间，传统的二进制提升（"树上倍增"）膨胀到 O(nlog⁡n)O(n \log n) 空间。 我们哪里做错了？
更仔细地看二进制提升结构，我认为它基本上只是应用于数组的"稀疏表"。这就是为什么一些论文称之为 "st-tree"，据我所知。 真正的问题是：我们如何将那种优雅的线段树带到树上？
PLAIN
        *
       / \
      *   *            ^
     /     \           |
....*.......*....      |
   /         \         |
  *           * <-- u  v
 /             \
*               *
关键洞察是：看图。我们在其中点（虚线）处切割树。对于节点 uu，我们不需要存储 uu 和其第 2 个祖先之间的信息，因为这个范围在我们的线段树中不存在。用树的语言来说，它穿过了虚线。

从线段树得到启发

要实现这个想法，我们先来看看线段树中每个右端点对应的区间长度：
CPP
              8
          4   4
        2 2 2 2 2 2
       111111111111
-------------------
index  123456789012
lowbit 010201030102
规律很明显：对于右端点 rr，对应的区间长度是 20,21,…,2lowbit(r)2^0, 2^1, \dots, 2^{\text{lowbit}(r)}。
那么在树上呢，对于一个深度为 depth(u)\text{depth}(u) 的节点 uu，我们只需要存储长度为 20,…,2lowbit(depth(u))2^0, \dots, 2^{\text{lowbit}(\text{depth}(u))} 的跳跃。

但是等一下...

看起来我们搞定了？O(n)O(n) 空间，每次加元素 O(1)O(1) 时间... 哎不对，这只是对一条路径有效！
考虑这棵树：
CPP
      *
      |
      *
      .
      .
      *
    / | \  ....
   *  *  * .... (最下面有很多叶子)
你看，最下面突然可以有很多叶子节点，每个叶子都要存 O(log⁡n)O(\log n) 个跳跃！这下空间又爆了...

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

这引导我去考虑一个"斜着"的线段树结构：
PLAIN
       (------------------------------)
       (-------------)(--------------)
       (-----)(-----) (-----)(-----)
       (-)(-) (-)(-)  (-)(-) (-)(-)
       ** **  ** **   ** **  ** **
--------------------------------------
                1111111111222222222233
index  1234567890123456789012345678901
这里的美妙之处是：对于每个右端点 rr，只有 1 个区间与之相关联！我们记作 (r−L(r),r](r - L(r), r]。我们可以观察到存在 k∈N+k \in \mathbb{N}^+ 使得 L(r)=2k−1L(r) = 2^k - 1。
现在还不清楚如何高效地决定 L(r)L(r)，所以让我们暂时假设它是给定的。首先，让我们看看如何建树和如何查询。
如何建树：下面我们将使用"节点"而不是"右端点"。对于节点 uu，它的和 sum⁡(u)\operatorname{sum}(u)（存储的跳跃的和）可以计算为：
sum⁡(u)=sum⁡(w)+sum⁡(v)+xu.\operatorname{sum}(u) = \operatorname{sum}(w) + \operatorname{sum}(v) + x_u.
如图所示：
PLAIN
	 u
	 |
	 v
(-----)
(-)(-)
 ^  ^
 |  |
 w  v
从这个更新，我们也知道如何确定 L(u)L(u)：
  • 如果前两个区间长度 L(v)L(v) 和 L(w)L(w) 相等，L(u)=2 L(w)+1L(u) = 2 \, L(w) + 1
  • 否则，它应该是 11
如何查询：要查询 (r−x,r](r - x, r]，有两种情况：
  • 如果 x≥L(r)x \geq L(r)，我们取 (r−L(r),r](r - L(r), r] 并跳到 r−L(r)r - L(r)
  • 否则，我们取元素，并继续 (r−(x−1),r−1](r - (x - 1), r - 1]
至此，我们终于得到了一个 O(n)O(n) 空间和 O(1)O(1) 更新的结构（O(log⁡n)O(\log n) 查询）。
附注：我之前有过一个非常类似的困惑 - LCT 在 O(log⁡n)O(\log n) 时间内解决树路径查询，即使有形状变化，而轻重链分解即使对于静态树也总是需要 O(log⁡2n)O(\log^2 n)。这让我想知道它们之间是否有更深的联系。而现在我们知道，还有"全局平衡二叉树"。（有趣的是，这个想法已经在杨哲的 2008 年集训队作业《QTREE 解法研究》中有详细记录，该文章向中国竞技编程社区介绍了 HLD。）

评论

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

正在加载评论...