静态区间最值查询（RMQ）

静态查询接口 ​

给定全序集合上的静态数组公理库数组Array以连续整数下标支持随机访问的有限序列结构。 $A[0\dots n-1]$，区间最小值查询接收满足 $0\le l<r\le n$ 的半开区间 $[l,r)$，返回

$${\mathrm{RMQ}}_A(l,r)=min\{i\in [l,r):A[i]=\underset{l\le j<r}{min}A[j]\}.$$

外层的最小值固定“并列时返回最左索引”。若应用只需要最小值，可以再读取 $A[{\mathrm{RMQ}}_A(l,r)]$；反过来只返回数值会丢掉位置，无法区分相同最小值的多个元素，也会让基于索引的归约失去确定性。

“静态”表示预处理完成后数组不再修改。输入若允许点更新、区间更新或版本切换，就已经成为不同问题，不能直接继承静态 RMQ 的复杂度。

一个带并列值的查询 ​

取 $A=(4,2,5,2,7)$。在本页的半开区间约定下，

$${\mathrm{RMQ}}_A(1,4)=1,$$

因为位置 $1$ 与 $3$ 的值同为 $2$，最左规则选择位置 $1$。查询 $[2,5)$ 则返回位置 $3$。如果另一资料使用闭区间 $[l,r]$，同样写成 RMQ(1,4) 会包含不同元素；比较算法或测试数据前必须先统一端点约定。

朴素基线逐项扫描查询区间，预处理为 $O(1)$，额外空间为 $O(1)$，单次查询为 $O(r-l)$。它虽然不快，却完整实现了接口，也说明 RMQ 问题本身不依赖任何高级数据结构。

三维成本 ​

静态 RMQ 解法至少要同时报告：预处理时间、额外空间和最坏查询时间。只写“$O(1)$ 查询”会隐藏可能很大的表，也无法说明一次性查询是否值得预处理。

Sparse Table公理库稀疏表Sparse table预计算长度为二次幂的静态区间答案，以 $O(1)$ 或 $O(\log n)$ 回答区间查询。利用最小运算的幂等性，让两个可能重叠的二次幂区间覆盖查询；它以 $O(n\log n)$ 预处理和空间换取 $O(1)$ 查询。线段树公理库线段树Segment tree把区间递归分解为规范节点，并在每个节点保存幺半群聚合值的平衡树结构。通常给出线性空间与 $O(\log n)$ 查询，同时更容易支持更新。基于笛卡尔树、LCA 与微块分类的结构还能达到线性预处理、线性空间和常数查询。三条路线解决同一接口，但不共享同一表示或证明。

问题边界 ​

RMQ 的最小运算具有幂等性，重叠覆盖不会改变答案。区间和却会把重叠部分重复计数，所以 Sparse Table 的同一查询公式不能原样迁移到任意区间聚合问题。

点更新也会使覆盖该位置的许多预计算区间同时过期。若题目要求更新后的查询，应在问题定义中写出操作序列和两类操作的成本，而不是把动态能力当成某个静态实现的附加优化。

RMQ 与最近公共祖先之间存在经典归约，但归约依赖 Euler tour、深度数组和稳定的并列规则。本页只固定被求解的问题；归约构造和常数查询实现由各自页面承担。

参考资料

• Bender, Farach-Colton, “The LCA Problem Revisited,” 2000.
• Fischer, Heun, “Space-Efficient Preprocessing Schemes for RMQ,” 2011.