线性预处理常数时间 RMQ

问题、约定与总复杂度 ​

给定长度 $n$ 的静态数组 $A$，查询半开区间 $[l,r)$ 中最左最小值的位置。固定最左 tie-breaking 很重要：Cartesian tree、Euler tour 和查表都必须返回同一个位置，不能只保证最小值相等。

在字长 $w=\mathrm{\Omega }(\log n)$、支持常数时间位运算与表寻址的 Word-RAM 上，可用

$$O(n)\text{预处理时间},O(n)\text{空间},O(1)\text{最坏查询时间}$$

回答所有静态 RMQ。下面先解决相邻差恒为 $\pm 1$ 的深度数组，再通过 RMQ–LCA 等价归约公理库RMQ 与 LCA 的等价归约RMQ-LCA equivalence · RMQ to LCA reduction用 Euler 深度序列与 Cartesian tree 建立静态 RMQ 和 LCA 的双向线性归约。处理一般数组。

从一般 RMQ 到正负一 RMQ ​

以 $A$ 的最左最小值规则建立 Cartesian tree：中序顺序等于数组下标，堆序按 $(A[i],i)$ 的字典序决定。于是

$${\mathrm{RMQ}}_A(l,r)={\mathrm{LCA}}_{C(A)}(l,r-1).$$

对 Cartesian tree 做完整 Euler walk，记录访问顶点 $E[j]$ 及深度 $D[j]$。沿一条树边向下或向上一步，故

$$D[j+1]-D[j]\in \{-1,+1\}.$$

两个顶点首次出现位置之间的最小深度项对应其 LCA。建树、Euler walk 和首次位置表都为 $O(n)$，因此只需在线性成本内解决数组 $D$ 上的 $\pm 1$ RMQ。

微块类型与查表成本 ​

令

$$b=max(1,\lfloor \frac{1}{2}{\log }_{2}n\rfloor )$$

并把 $D$ 划分为长度至多 $b$ 的连续微块。一个满块在减去首项后，只由 $b-1$ 个正负一增量决定，所以类型数至多

$$2^{b-1}=O(\sqrt{n}).$$

同一类型内，每个相对区间 $[p,q)$ 的最左最小位置都相同。为每种类型预计算全部 $O(b^2)$ 个区间答案，总表大小和建表时间为

$$O(2^b{b}^2)=O(\sqrt{n}{\log }^{2}n)=o(n).$$

每个实际微块只保存其类型编号、首值和全块最小值位置，共 $O(n/b)$ 项。类型可由增量的正负编码为一个 $b-1$ bit 字；微块查询由类型与两个块内端点做一次表查完成。最后不足 $b$ 的块可按长度与类型共同编号，仍不改变上述数量级。

宏结构为何仍是线性的 ​

设微块数为

$$N=\lceil \frac{n}{b}\rceil .$$

建立数组 $M[j]$，保存第 $j$ 个微块的最左最小位置，并以对应深度作比较键。对 $M$ 建 稀疏表公理库稀疏表Sparse table预计算长度为二次幂的静态区间答案，以 $O(1)$ 或 $O(\log n)$ 回答区间查询。，预处理和空间为

$$O(N\log N)=O(\frac{n}{\log n}\log n)=O(n),$$

而完整微块区间的最小值可在 $O(1)$ 查询。这里使用 sparse table 并没有重新引入 $O(n\log n)$：宏数组比原数组缩小了一个 $\mathrm{\Theta }(\log n)$ 因子。

总预处理由 Euler 归约 $O(n)$、实际微块扫描 $O(n)$、通用类型表 $o(n)$ 和宏稀疏表 $O(n)$ 组成，故整体仍是 $O(n)$。

查询分成至多三个候选 ​

若 $[l,r)$ 落在同一微块，直接查该类型的局部表。否则把区间分为：

1. 从 $l$ 到其微块末尾的左残块；
2. 中间若干完整微块；
3. 右侧微块开头到 $r$ 的右残块。

左右残块各做一次微表查询，中间部分做一次宏稀疏表查询；比较至多三个候选的 $(D[i],i)$，返回最左者，查询最坏 $O(1)$。

例如一个查询从第 $j$ 块中部进入、在第 $j+3$ 块中部结束，算法不会逐项扫描四个块：只查第 $j$ 块的后缀、第 $j+1$ 到 $j+2$ 两个整块的宏答案，以及第 $j+3$ 块的前缀。三个答案覆盖查询区间且互不遗漏。

失败边界与近邻方案 ​

类型数 $2^{b-1}$ 依赖相邻深度差恰为 $\pm 1$。一般数值块即使减去首值仍可能有巨大类型空间，不能原样查表；一般 RMQ 必须先通过 Cartesian tree 与 Euler tour 获得这条特殊结构。

通用类型表可以按机器规模共享，也可以计入当前实例；即使逐实例构造，它也是 $o(n)$。若机器字装不下类型编码、表寻址不是常数时间，或表被视为不可用的非一致 advice，模型已经改变，$O(1)$ 查询结论需重新解释。

稀疏表本身预处理简单但占 $O(n\log n)$；本结构用微宏分解把它只放在缩小后的宏数组上。线段树支持更新却只能给对数查询。这里的最优界严格属于静态 RMQ，数组一旦点更新，Cartesian tree、块类型和宏最小值都可能同时失效。

参考资料

• Michael A. Bender and Martín Farach-Colton, “The LCA Problem Revisited,” LATIN 2000, LNCS 1776, 88–94.
• Johannes Fischer and Volker Heun, “Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE,” CPM 2006.
• Dov Harel and Robert E. Tarjan, “Fast Algorithms for Finding Nearest Common Ancestors,” SIAM Journal on Computing 13(2), 1984.