算法与数据结构 / RMQ 与 LCA · 同一个问题的两种形态 待审核 6 页

RMQ 与 LCA · 同一个问题的两种形态

两个看起来毫不相干的问题。一个在数组上：给定不再修改的 $a[0..n-1]$ ，反复问「 $a[l..r]$ 的最小值是多少」，这是 RMQ（range minimum query）。另一个在树上：给定一棵有根树，反复问「 $u$ 与 $v$ 最深的那个公共祖先是谁」，这是 LCA（lowest common ancestor）。

本系列要说的是它们其实是一个问题。欧拉序把 LCA 变成 RMQ：把 DFS 的进入与回溯全都记下来，得到一条长 $2n-1$ 的序列，两点的 LCA 就是它们首次出现位置之间深度最小的那个节点。笛卡尔树把 RMQ 变成 LCA：按「中序是原下标、堆序是值」建树， $a[l..r]$ 的最小值位置就是下标 $l$ 与 $r$ 在树上的 LCA。两条归约都是线性时间的，于是任一侧的解法都能拿去解另一侧。

路线是：先在静态数组上把 sparse table 讲透——预处理 $O(n \log n)$ 、查询 $O(1)$ ，代价是数组不能再改；再上树，倍增给出 $O(\log n)$ 的在线查询，欧拉序把它压到 $O(1)$ ，Tarjan 用一遍 DFS 加并查集把全部询问离线做完；最后用笛卡尔树把圈闭上，并交代 $O(n)$ – $O(1)$ 的 ±1 分块是怎么来的。

静态数组：用空间换 O(1) 查询

sparse table 预先算好所有「长度为 2 的幂」的区间，查询时用两段长度相同的区间重叠覆盖 $[l, r]$ 。它成立的前提是聚合运算 idempotent—— $\min(a, a) = a$ ，重叠算两次也无妨。求和不满足这一条，同一套查询法在它身上每一个区间都给错数。

sparse table · idempotent

sparse table：预处理换 O(1) 查询

数组不再修改时，预先算好所有「长度为 2 的幂」的区间，任何查询都能用两段重叠覆盖，一次比较出答案。这套查询法成立的唯一前提是聚合运算 idempotent，求和不满足它，于是每一个区间都算错。

idempotent 不是可有可无的细节

两段覆盖里的重叠格数是

2 \cdot 2^k - \text{len}

，而

2^k \le \text{len} < 2^{k+1}

，所以这个量恒不小于 1——两段永远至少重一格，

\text{len}

恰为 2 的幂时更是完全重合。于是求和版不是「有时算错」而是「一个都对不了」：全 1 的 32 元数组上，528 个区间无一正确，长度为 2 的幂的那些恰好翻倍（见 sparse table §4）。可修改、可求和的那一侧属于前缀和与线段树的地盘，两者解决的不是同一类需求。

sparse table · 延伸阅读

Sparse Table cp-algorithms.com 建表递推、两段覆盖的查询、idempotent 与非 idempotent 两类聚合的分别处理，以及不相交稀疏表 (disjoint sparse table) 变体。
Range minimum query en.wikipedia.org RMQ 的问题定义与各解法的复杂度对照表，含 $O(n)$ – $O(1)$ 一路的历史脉络。

树上：三条通向 LCA 的路

倍增预存每个节点的第 $2^k$ 级祖先，查询按二进制位跳，在线且实现最短。欧拉序把树摊平成序列，LCA 随即变成 RMQ，查询降到 $O(1)$ 。Tarjan 反其道而行：先收齐全部询问，一遍 DFS 配并查集把它们一次算完，代价是不接受「边问边答」。

binary lifting · O(log n) 查询

树上倍增：按二进制位往上跳

预存每个节点的第 $2^k$ 级祖先，任何一次上跳都能拆成若干次查表。LCA 查询分两个阶段：先把深的一方提到同深，再从高位到低位同步上跳，停在「跳一步就重合」的位置。

euler tour · 归约 · O(1) 查询

欧拉序：把 LCA 归约成区间最值

把 DFS 的每次进入与每次回溯都记一笔，得到一条长 2n−1 的序列。两点的 LCA 就是它们首次出现位置之间深度最小的那个节点，于是 LCA 整个变成了 RMQ。

offline · union-find · α(n)

Tarjan 离线：一遍 DFS 配并查集

先把全部询问收齐，再做一次 DFS。回溯时把子树并进父亲，某个节点被染黑之后，它所在集合的 ancestor 就是它与当前节点的 LCA。总代价随 n + q 线性，代价是不接受边问边答。

三种实现的分工判据

先看询问是否可以攒着。全部询问事先已知——离线可行——Tarjan 的总量随

n + q

线性，常数也最小；一旦要求边问边答，它就不适用。在线的两者之间再看

q

与

n

的相对大小。

q

远小于

n

时倍增更划算：它的预处理量是

(\lceil \log_2 n \rceil + 1) \cdot n

，比欧拉序在长度

2n-1

的序列上建稀疏表要少（

n = 100000

时实测 1700000 对 3137858）。

q

与

n

同量级或更大时反过来，欧拉序每次查询只做一次比较，倍增每次要读约

2\log n

个表项。

LCA 的三种实现 · 延伸阅读

LCA with Binary Lifting cp-algorithms.com 倍增表的建法与查询的两个阶段，含「跳到仍不相同为止」这一写法为何比「跳到相同」更好实现。
Tarjan, R. E. (1979). Applications of Path Compression on Balanced Trees dl.acm.org 离线 LCA 的出处，与并查集路径压缩的摊还分析同源。
Tarjan's off-line LCA algorithm en.wikipedia.org 伪代码与不变量的简明陈述：处理到 $v$ 时，已染黑的节点所在集合的 ancestor 就是它与 $v$ 的 LCA。

闭环：两个问题互为对方

笛卡尔树给出反方向的归约，RMQ 由此变成 LCA。两条归约拼在一起，就有了 $O(n)$ – $O(1)$ 的可能：欧拉序的深度数组相邻差恒为 $\pm 1$ ，这条额外性质让块内形态只有 $2^{b-1}$ 种，可以全部预先打表。

Cartesian tree · ±1 RMQ · O(n)–O(1)

笛卡尔树：把 RMQ 变回 LCA

中序是原下标、堆序是值的那棵树，让区间最小值变成两个下标的 LCA。与欧拉序那条归约合起来，RMQ 与 LCA 互为对方；±1 性质再把预处理压到线性。

树上距离 · 虚树 · 树链剖分

这套地基撑起了什么

LCA 一旦是常数或对数级的，树上距离、路径上的第 k 个点、虚树、树链剖分都随之成立。本页逐个交代这些出口，并说明各自依赖前面哪一条结论。

归约与 O(n)–O(1) · 延伸阅读

Bender, M. A., & Farach-Colton, M. (2000). The LCA Problem Revisited cs.tau.ac.il 把 LCA 归约到 ±1 RMQ、再用块内打表做到 $O(n)$ – $O(1)$ 的标准讲法，本系列末两页依此组织。
Cartesian tree en.wikipedia.org 定义、单调栈线性构造，以及与 treap、笛卡尔树排序、RMQ 的关系。
Fischer, J., & Heun, V. (2006). Theoretical and Practical Improvements on the RMQ-Problem citeseerx.ist.psu.edu 不必显式建树的 $O(n)$ 方案，用笛卡尔树的形态编号做块内索引，实践中比 Bender–Farach-Colton 更省。