RMQ (区间最值查询) 模板详解
1. 简介
RMQ（Range Minimum
Query）是一种用于解决区间最值查询问题的数据结构。它能够在 O(1)
的时间复杂度内查询任意区间的最小值（或最大值）。本模板采用了 ST
表（Sparse Table）和分块优化的混合策略，实现了更高效的查询。
主要特点：
- 支持任意类型的比较操作
- 预处理时间复杂度 O(n log n)
- 查询时间复杂度 O(1)
- 空间复杂度 O(n log n)
2. 实现原理
2.1 基本结构
该实现结合了多种优化技术：
- ST 表用于处理大区间查询
- 分块处理用于优化小区间查询
- 预处理块内前缀最小值和后缀最小值
- 使用位运算优化块内查询
2.2 核心策略
分块处理：
- 将数组分成固定大小（64）的块
- 对每个块预处理内部信息
ST 表优化：
- 用于处理跨越多个块的查询
- 保证 O(1) 的查询时间复杂度
前缀/后缀数组：
- pre[] 存储每个位置到所在块开始的最小值
- suf[] 存储每个位置到所在块结束的最小值
位运算优化：
- 使用 64 位整数存储块内状态
- 通过位运算快速查询块内最小值
3. 模板代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| template<class T, class Cmp = std::less<T>>
struct RMQ {
const Cmp cmp = Cmp();
static constexpr unsigned B = 64;
using u64 = unsigned long long;
int n;
std::vector<std::vector<T>> a;
std::vector<T> pre, suf, ini;
std::vector<u64> stk;
RMQ() {}
RMQ(const std::vector<T> &v) {
init(v);
}
void init(const std::vector<T> &v) {
n = v.size();
pre = suf = ini = v;
stk.resize(n);
if (!n) {
return;
}
const int M = (n - 1) / B + 1;
const int lg = std::__lg(M);
a.assign(lg + 1, std::vector<T>(M));
for (int i = 0; i < M; i++) {
a[0][i] = v[i * B];
for (int j = 1; j < B && i * B + j < n; j++) {
a[0][i] = std::min(a[0][i], v[i * B + j], cmp);
}
}
for (int i = 1; i < n; i++) {
if (i % B) {
pre[i] = std::min(pre[i], pre[i - 1], cmp);
}
}
for (int i = n - 2; i >= 0; i--) {
if (i % B != B - 1) {
suf[i] = std::min(suf[i], suf[i + 1], cmp);
}
}
for (int j = 0; j < lg; j++) {
for (int i = 0; i + (2 << j) <= M; i++) {
a[j + 1][i] = std::min(a[j][i], a[j][i + (1 << j)], cmp);
}
}
for (int i = 0; i < M; i++) {
const int l = i * B;
const int r = std::min(1U * n, l + B);
u64 s = 0;
for (int j = l; j < r; j++) {
while (s && cmp(v[j], v[std::__lg(s) + l])) {
s ^= 1ULL << std::__lg(s);
}
s |= 1ULL << (j - l);
stk[j] = s;
}
}
}
T operator()(int l, int r) {
if (l / B != (r - 1) / B) {
T ans = std::min(suf[l], pre[r - 1], cmp);
l = l / B + 1;
r = r / B;
if (l < r) {
int k = std::__lg(r - l);
ans = std::min({ans, a[k][l], a[k][r - (1 << k)]}, cmp);
}
return ans;
} else {
int x = B * (l / B);
return ini[__builtin_ctzll(stk[r - 1] >> (l - x)) + l];
}
}
};
|
4. 函数说明
4.1 构造函数和初始化
1
2
3
| RMQ() {}
RMQ(const std::vector<T> &v)
void init(const std::vector<T> &v)
|
- 支持默认构造和基于数组的构造
init 函数完成所有预处理工作- 支持自定义比较函数
4.2 查询函数
1
| T operator()(int l, int r)
|
- 查询区间 [l, r) 内的最小值
- 根据查询区间是否跨块采用不同策略
- 返回区间最小值
5. 时间复杂度分析
初始化：O(n log n)
- ST 表构建：O(n log n)
- 分块预处理：O(n)
- 前缀/后缀数组：O(n)
查询：O(1)
- 同块查询：O(1)，使用位运算
- 跨块查询：O(1)，使用 ST 表
空间复杂度：O(n log n)
- ST 表：O(n log n)
- 其他数组：O(n)
6. 应用场景
- 区间最值查询问题
- 可视化最近点对问题
- 最长公共前缀（LCP）问题
- 区间 GCD 查询
- 各种需要快速查询区间统计信息的场景
7. 注意事项
- 模板支持自定义比较函数，可以查询最大值或其他统计量
- 查询区间为左闭右开 [l, r)
- 分块大小设为 64 是为了优化位运算操作
- 初始化时需要足够的内存空间
8. 总结
RMQ 是一个强大的数据结构，本模板通过结合 ST
表和分块思想，实现了高效的区间查询。它的实现虽然较为复杂，但查询效率极高，是解决区间最值问题的理想选择。
