RMQ

释义 Definition

RMQ 是 Range Minimum Query 的缩写，指“区间最小值查询”：在一个数组/序列中，反复询问某个区间 [l, r] 里的最小元素是多少。它常见于算法与数据结构题中，可用线段树、稀疏表等方法高效处理。（在不同领域里 RMQ 也可能有其他含义，但计算机算法语境中这一义最常见。）

发音 Pronunciation (IPA)

/ˌɑːr ɛm ˈkjuː/

例句 Examples

We can answer RMQ in O(1) time after preprocessing.
预处理之后，我们可以用 O(1) 时间回答 RMQ（区间最小值查询）。

The sparse table method is efficient for static RMQ, but it doesn’t support updates well.
稀疏表方法对静态 RMQ 很高效，但不太适合需要频繁更新的数据。

词源 Etymology

RMQ 属于首字母缩略词：由 Range（区间）+ Minimum（最小值）+ Query（查询）各取首字母组成，常在算法论文、竞赛与工程文档中使用。

相关词 Related Words

• Segment Tree
• Sparse Table
• Query
• Data Structure
• LCA
• Preprocessing
• Time Complexity

文学与著作中的用例 Literary Works

• Competitive Programming（Steven Halim 等）：在讲解区间查询/数据结构时常出现 RMQ。
• *Introduction to Algorithms (CLRS)*（Cormen 等）：在相关的区间查询、数据结构主题中会涉及 RMQ 思想与问题变体。
• Programming Challenges（Skiena & Revilla）：在竞赛题型与经典问题讨论中可见 RMQ/区间查询相关表述。