Range Minimum Query

释义 Definition

Range Minimum Query（区间最小值查询，常缩写为 RMQ）：在一个数组/序列中，给定多个查询区间 ([l, r])，需要快速返回该区间内的最小元素值（或最小值的位置）。常见做法会先进行预处理，以便多次查询更高效。（相关问题还包括区间最大值、区间和等“区间查询”。）

发音 Pronunciation (IPA)

/reɪndʒ ˈmɪnɪməm ˈkwɪəri/

例句 Examples

We use a sparse table to answer range minimum queries in O(1) time after preprocessing.
我们用稀疏表预处理后，可以用 O(1) 时间回答区间最小值查询。

In competitive programming, the range minimum query problem is often paired with LCA to compute distances on trees efficiently.
在竞赛编程中，区间最小值查询常与最近公共祖先（LCA）结合，用来高效计算树上的距离等问题。

词源 Etymology

这是一个计算机科学/算法领域的组合术语：range（区间）+ minimum（最小值）+ query（查询）。随着需要对同一序列进行大量区间查询的应用增多（如检索、统计、图与树算法），RMQ 逐渐成为经典基础问题之一，并衍生出多种数据结构与预处理解法（如线段树、稀疏表等）。

相关词 Related Words

• Segment Tree
• Sparse Table
• Fenwick Tree
• Interval
• Query
• Preprocessing
• LCA
• Data Structure
• Algorithm

文学与著作 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein；常称 CLRS）：在“数据结构/区间查询”的相关语境中讨论区间问题与思想，可作为 RMQ 背后方法论的权威参考。
• Competitive Programming（Halims）：竞赛编程经典书，RMQ（尤其稀疏表、线段树等解法）是高频主题之一。
• The Algorithm Design Manual（Steven S. Skiena）：以问题导向讲解常见算法设计与数据结构，区间查询类问题常作为典型应用场景出现。