区间最值（RMQ）三种经典解法详解
关键词：RMQ、区间最小值、分块、线段树、Sparse Table（ST 表）
区间最值（Range Minimum Query，RMQ）是算法竞赛和日常算法练习中非常经典的一类问题。
本文将围绕这样一个基础模型，系统讲解三种常见解法：分块、线段树、ST 表，从「为什么要这样做」到「适合什么场景」，尽量用直观的方式解释清楚。
一、问题模型
给定一个长度为 n 的数组 a[1..n]，接下来有 q 次询问，每次询问一个区间 [l, r]，要求输出该区间内的最小值。
- 数组下标从 1 开始
- 数组 不发生修改（非常关键）
n, q最大可达10^5
这是一个典型 RMQ 问题。
二、为什么暴力不行？
最直观的想法是：
- 每次询问时，遍历区间
[l, r]，找最小值
但复杂度是：
O(q × n)在 n = q = 10^5 的情况下，必然超时。
因此，我们需要通过 预处理，让每次查询更快。
三、方法一：分块（√ 分治思想）
1. 核心思想
把数组划分为若干个大小约为 √n 的块：
- 每一块提前计算好最小值
- 查询时：
- 整块 → 直接使用块最小值
- 零散部分 → 暴力扫描
这是一种用空间换时间的方式。
2. 实现思路
- 块大小：
block = sqrt(n) - 第
i个元素属于：i / block号块 - 维护数组：
block_min[k] = 第 k 块的最小值3. 查询过程
查询 [l, r] 时：
- 若
l和r在同一块：直接暴力 - 否则：
- 左边零碎部分暴力
- 中间整块直接取
block_min - 右边零碎部分暴力
4. 复杂度分析
| 项目 | 复杂度 |
|---|---|
| 预处理 | O(n) |
| 单次查询 | O(√n) |
5. 特点总结
- 实现简单
- 思想直观
- 性能一般
- 适合作为 RMQ 的入门方法
四、方法二：线段树（递归区间结构）
1. 核心思想
把区间不断二分，构成一棵树：
- 每个节点代表一个区间
[l, r] - 节点保存该区间的最小值
根节点表示 [1, n]，叶子节点表示单个元素。
2. 结构示意
[1, n]
/ \
[1, mid] [mid+1, n]3. 查询过程
查询 [l, r] 时：
- 当前区间完全包含于
[l, r]→ 直接返回 - 完全不相交 → 忽略
- 部分相交 → 递归左右子区间
4. 复杂度分析
| 项目 | 复杂度 |
|---|---|
| 建树 | O(n) |
| 单次查询 | O(log n) |
5. 线段树的优势
- 支持区间最值
- 支持区间修改、单点修改
- 非常通用
缺点：实现相对复杂，常数较大。
五、方法三：Sparse Table（ST 表）⭐
这是解决静态 RMQ 的最优方案之一。
1. 核心思想
预处理所有长度为 2^k 的区间最小值。
任意区间都可以由 两个重叠的 2 的幂区间 覆盖。
2. 定义
st[i][j]
= 从 i 开始，长度为 2^j 的区间最小值3. 预处理递推
- 初始化：
st[i][0] = a[i]- 状态转移：
st[i][j] = min(
st[i][j-1],
st[i + (1<<(j-1))][j-1]
)4. 查询 [l, r]
len = r - l + 1
k = floor(log2(len))
答案 = min(
st[l][k],
st[r - (1<<k) + 1][k]
)5. 复杂度分析
| 项目 | 复杂度 |
|---|---|
| 预处理 | O(n log n) |
| 单次查询 | O(1) |
6. 注意事项
- 数组必须是静态的（不能修改）
- 内存消耗略大
六、三种方法对比总结
| 方法 | 单次查询 | 是否支持修改 | 适用场景 |
|---|---|---|---|
| 分块 | O(√n) | ❌ | 入门理解 |
| 线段树 | O(log n) | ✅ | 动态区间问题 |
| ST 表 | O(1) | ❌ | 静态 RMQ |
七、如何快速选择算法？
- 数组不修改 + 多次区间最值查询 → ST 表
- 需要修改数组 → 线段树
- 想快速写一个不太慢的版本 → 分块
八、结语
RMQ 是区间问题的起点：
- 学会分块，可以理解“预处理”的价值
- 学会线段树，可以应对大多数区间问题
- 学会 ST 表，可以解决静态 RMQ 的极致优化
掌握这三种方法，基本可以覆盖 90% 的区间最值问题。
完。
版权所有
版权归属：PushTracer