静态区间最值查询（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)$ 查询。加入单点更新、区间加法或一般非幂等聚合后，接口已经改变，不能继续沿用该静态常数时间结论。

静态 RMQ 可用稀疏表、线性空间结构或 RMQ–LCA 归约实现，并服务于 LCA、后缀数组 LCP 与简洁树导航。需要更新、求和或其他非幂等聚合时，应重新选择接口与结构，而不能只替换“min”运算符。