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

笛卡尔树：把 RMQ 变回 LCA

欧拉序把 LCA 化归成了 RMQ。本页做反方向：给任意数组造一棵树，使得数组上的区间最小值等于树上的 LCA。两条归约拼起来，两个问题就是同一个问题的两种写法。

1 · 定义

定义 1.1（Cartesian tree） 数组 $a[0..n-1]$ 的笛卡尔树是这样一棵二叉树：中序遍历给出下标序列 $0, 1, \dots, n-1$ ；每个节点的值不大于两个孩子的值。

两条约束一起把树钉死。中序那一条说明树的形状必须与下标顺序相容，堆序那一条说明根一定是全局最小值所在的位置；根把数组切成左右两半，左右子树递归地是这两半的笛卡尔树。值互不相同时，这棵树唯一。

2 · 单调栈线性构造

递归定义给出的是 $O(n^2)$ 最坏（每次找区间最小值）。线性做法从左往右扫，维护一个栈。

栈里始终装着当前树的最右一条链：从根往下、值递增。新下标 $i$ 到来时，把所有值大于 $a[i]$ 的弹出；最后弹出的那个成为 $i$ 的左孩子，弹完之后的栈顶成为 $i$ 的父亲， $i$ 自己压进栈。

正确性来自两条对应：被弹出的那一串在数组里都排在 $i$ 左边且值都比 $a[i]$ 大，正好符合「中序在左、堆序在下」；留在栈里的栈顶值不大于 $a[i]$ ， $i$ 只能挂成它的右孩子。

每个下标进栈一次、至多出栈一次，总操作数不超过 $2n$ 。12 项的演示数组实测 20 次（末尾还有 4 个下标留在栈里没弹）。

图 2-1 · 单调栈逐个插入下标：数组、栈与树同步变化。可换数组（含有序输入这一退化情形）并单步执行。

比较用严格大于还是不小于，决定了并列值里谁当祖先。用严格大于时，同值的先来者留在栈里、后来者挂成它的右孩子，区间里最左的最小值因而成为祖先：60 项、值域只有 4 的数组上，全部 1830 个区间的 LCA 都等于最左 argmin。换成不小于弹栈，1830 个区间里有 1631 个改判成最右 argmin。两种写法给出的最小值都对，只是「哪个位置」不同；要与朴素扫描的 argmin 逐个对上，就得挑与朴素扫描同侧的那个写法。

3 · 归约

定理 3.1 设 $T$ 是 $a$ 的笛卡尔树。对任意 $i \le j$ ， $a[i..j]$ 的最小值所在位置就是节点 $i$ 与节点 $j$ 在 $T$ 上的 LCA。

证明记 $w = \text{LCA}(i, j)$ 。中序遍历给出下标序，而一个节点的中序邻域恰是它的子树； $i$ 与 $j$ 都在 $w$ 的子树内，且分居 $w$ 的两侧（或其一等于 $w$ ），所以 $[i, j]$ 整段落在 $w$ 的子树里，且 $w \in [i, j]$ 。

堆序说明 $w$ 的值不大于它子树内任何节点的值， $[i, j]$ 里的每个下标都在这棵子树内，故 $a[w] = \min_{i \le t \le j} a[t]$ 。 $\blacksquare$

图 3-1 · 同一个区间的答案在数组侧与树侧同时高亮，下方表格列出四条独立路径给出的结果。可拖动区间两端观察 LCA 随之移动。

于是两条归约都在手上：欧拉序把 LCA 变成 RMQ，笛卡尔树把 RMQ 变成 LCA，两者都是 $O(n)$ 的。任一侧的算法都能拿去解另一侧，复杂度只差一个线性项。

警示 · 归约本身线性，不代表套上去就快。笛卡尔树的形状随数据而变：随机数组上 4096 个元素的树高实测在 23 到 32 之间（20 个种子），约 $2.3\log_2 n$ ；有序数组直接退化成一条 4095 长的链。所以「建笛卡尔树再爬 parent 求 LCA」在最坏情形是 $O(n)$ 每次，比朴素扫描还慢。归约要配 $O(1)$ 的 LCA 才有意义，而 $O(1)$ 的 LCA 又要经欧拉序绕回 RMQ。

4 · ±1 与块内打表

绕这一圈的收益在于：经笛卡尔树与欧拉序之后拿到的那个 RMQ 实例，比原来的一般 RMQ 多一条性质——相邻两项深度差恒为 $\pm 1$ （见欧拉序 §2）。

这条性质把「块内长什么样」的可能性压得极少。取块长 $b$ ，一块由 $b-1$ 个 $\pm 1$ 决定形态，只有 $2^{b-1}$ 种。取 $b = \lceil \log_2 m / 2 \rceil$ ，形态数是 $O(\sqrt{m})$ ，可以把所有形态的所有区间答案预先全部算出来存成一张表，之后块内任意查询就是一次查表。

块间只剩 $m / b$ 个代表元（每块的最小值）。在这些代表元上建稀疏表，规模是 $\frac{m}{b}\log\frac{m}{b}$ ；代入 $b \approx \frac{\log_2 m}{2}$ 得到 $\frac{2m}{\log_2 m} \cdot \log_2 m = 2m$ ，也就是线性。

图 4-1 · 分块参数在四个数量级上的实际取值，以及一个随机实例里真正出现过的块内形态。可改取样规模观察形态数与理论上界的差距。

$n = 10^6$ 时的实测： $m = 1999999$ ，块长 11，形态数 1024，块内表 67584 格（只占 $m$ 的 3.4%），块间稀疏表 3010617 格（ $1.5m$ ），合计 3078201，而同规模的朴素稀疏表是 39902849 格——省下 92.3%。

理论上界通常很松。 $n = 500$ 的随机实例切成 200 块、块长 5，上界 $2^4 = 16$ 种形态，实际出现 15 种。上界之所以够用，不是因为它紧，而是因为 $2^{b-1}$ 本身已经小到无所谓。

注 · 这套结构常被称作 Method of Four Russians，得名于 Arlazarov、Dinic、Kronrod、Faradzhev 1970 年那篇布尔矩阵乘法的论文（四位作者中只有一位是俄罗斯人，这个名字是后人起的）。共同的套路是：把问题切成 $O(\log)$ 大小的块，块的种类数因而是次线性的，于是可以对所有可能的块预先打表。Fischer 与 Heun 2006 年的做法更进一步，不显式建树，直接用块内笛卡尔树的形态编号当索引。

5 · 参考文献

Vuillemin, J. (1980). A unifying look at data structures. Communications of the ACM, 23(4), 229–239.
Gabow, H. N., Bentley, J. L., & Tarjan, R. E. (1984). Scaling and related techniques for geometry problems. In STOC '84 (pp. 135–143). ACM.
Bender, M. A., & Farach-Colton, M. (2000). The LCA problem revisited. In LATIN 2000: Theoretical Informatics (pp. 88–94). Springer.
Fischer, J., & Heun, V. (2006). Theoretical and practical improvements on the RMQ-problem, with applications to LCA and LCE. In Combinatorial Pattern Matching (pp. 36–48). Springer.
Arlazarov, V. L., Dinic, E. A., Kronrod, M. A., & Faradzhev, I. A. (1970). On economical construction of the transitive closure of a directed graph. Doklady Akademii Nauk SSSR, 194(3), 487–488.