静态区间最值查询（RMQ）

RMQ 预处理的是区间之间大量重叠的比较信息，而不是每次重新求最小值。不同结构在预处理时间、额外空间与查询时间之间分配这份信息；稳定的端点与并列规则让所有表项、笛卡尔树归约和返回位置具有同一语义。

一个带并列值的查询 ​

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

因为位置 $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 与最近公共祖先理路最近公共祖先Lowest common ancestor · LCA有根树中同时为两个顶点祖先且深度最大的唯一顶点及其查询问题。之间存在经典归约，但归约依赖 Euler tour、深度数组和稳定的并列规则。从数组到树与从树到深度序列的两个方向，分别把区间最小值和祖先查询转成彼此的接口。

线性预处理常数时间 RMQ理路线性预处理常数时间 RMQConstant-time RMQ · Farach-Colton–Bender RMQ · 线性 RMQ将一般静态 RMQ 归约为深度差为正负一的数组，再用微块类型查表与宏块稀疏表实现线性预处理、常数查询。通过笛卡尔树、Euler tour 与微块表等结构，把静态数组的比较信息组织成线性空间索引，每次查询用 $O(1)$ 时间返回最小值位置。这使大量重复查询能够分摊预处理成本。

后缀数组中，两后缀的最长公共前缀长度可由它们之间 LCP 数组的最小值求得；简洁树导航也会把部分树上查询转成区间最小值。