题解：P3865 【模板】ST 表 && RMQ 问题
superLouis
·
·
题解
题解：P3865 【模板】ST 表 && RMQ 问题
个人认为这是最详细的一篇题解了。
1. 算法介绍
所谓的 RMQ 问题，其实就是 Range Minimum / Maximum Query，也就是“区间最大 / 最小值查询”这类问题。而 ST 表就是 Sparse Table，也称稀疏表，是用于解决可重复贡献问题的数据结构。这种算法也是一种离线算法，我们在这里讲述查找最大值。
稀疏表的思想就是把所有区间长度为二的幂次的最值存入一个表中，就可以在恒定的时间回答任何查找范围。
| 2^0 |
2^1 |
2^2 |
2^3 |
| 1 |
[1,1] |
[1,2] |
[1,4] |
[1,8] |
| 2 |
[2,2] |
[2,3] |
[2,5] |
[2,9] |
| 3 |
[3,3] |
[3,4] |
[3,6] |
[3,10] |
| 4 |
[4,4] |
[4,5] |
[4,7] |
[4,11] |
| 5 |
[5,5] |
[5,6] |
[5,8] |
[5,12] |
| 6 |
[6,6] |
[6,7] |
[6,9] |
\varnothing |
| 7 |
[7,7] |
[7,8] |
[7,10] |
\varnothing |
| 8 |
[8,8] |
[8,9] |
[8,11] |
\varnothing |
| 9 |
[9,9] |
[9,10] |
[9,12] |
\varnothing |
| 10 |
[10,10] |
[10,11] |
\varnothing |
\varnothing |
| 11 |
[11,11] |
[11,12] |
\varnothing |
\varnothing |
| 12 |
[12,12] |
\varnothing |
\varnothing |
\varnothing |
（1）稀疏表的合并操作（建立）
在稀疏表内，记 st[i][j] 为以第 i 个元素为开头长度为 2^j 的区间最值。初始的时候，所有的 st_{i,0} 都等于 a_i。
对于每个 j>0 的 st_{i,j}，st_{i,j} = \max(st_{i,j-1}, st_{i+2^{j-1},j-1})。其实没你看着那么复杂，就是把长度为 2^j 区间分成两个长度为 2^{j-1} 的区间，两个小区间的起始坐标是 i 和 i + 2^{j-1}。下面给一张图，更加直观：
在这里，我们给出稀疏表的合并（建立）操作的代码：
void st_build() {
for (int i = 1; i <= n; i++) st[i][0] = a[i];
int t = log2(n); // 这里 t 是枚举时长度的上限
for (int j = 1; j <= t; j++)
for (int i = 1; i <= n - (1 << j) + 1; i++)
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
时间复杂度 \Theta(n \log n)
（2）稀疏表查询操作
说实话，最开始我想到的查询操作是 \Theta(\log n) 时间复杂度的。大概是这样：把要查询的区间进行二进制拆分，然后拆成最多 \log n 个互不重叠的区间，并将这些区间的最大值取 \max。实际上这样是大炮打蚊子——小题大做了。
所以，查询操作最简单的方式就是：
1. 当询问任意区间 $[l,r]$ 的最大值时，我们先计算出一个 $k$，满足：$2^k \le r–l+1 <2^{k+1}$。也就是在小于等于区间长度的前提下，找到最大的 $2$ 的 $k$ 次幂。
2. 此时，从“$l$ 开始的 $2^k$ 个数”，和“以 $r$ 结尾的 $2^k$ 个数”这两段一定覆盖 $[l,r]$（一般会有重合部分，但不影响答案）。
3. 这两段的最大值分别是 $st_{l,k}$ 和 $st_{r-2^k+1,k}$，两者的中的较大值就是整个区间 $[l,r]$ 中的最大值。
在这里，我们给出稀疏表查询操作的代码：
```cpp
int st_query(int l, int r) {
int k = log2(r - l + 1); // std::log2 的性能非常高，时间复杂度非常接近 Θ(1)
return max(st[l][k], st[r - (1 << k) + 1][k]);
}
```
这样下来，时间复杂度 $\Theta (1)$，完美！
----------
### 2. 正确性证明
先对合并（建立）操作进行正确性证明。对于每一个 $st_{i,j} (j > 0)$，都能毫不重合并且不遗漏任何地从 $st_{i,j-1}$ 和 $st_{i+2^{j-1},j-1}$ 推得。设 $i=a, i+2^j=b, i+2^j-1=c$ 并且记区间 $[p,q]$ 的最大值是 $f_{p,q}$，则 $f_{a,b} = \max(f_{a,c}, f_{c+1,b}) = \max(st_{i,j-1}, st_{i+2^{j-1}，j-1})$。
查询操作的正确性前面证明过，这里再写一遍。令 $l < i < j < r$ 并且记 $f_{p,q}$ 为区间 $[p,q]$ 的区间最大值，那么 $f_{l,r} = \max(f_{l,j},f_{j+1,r}) = \max(f_{l,i}, f_{i+1,r}) = \max(f_{l,j}, f_{i,r})$，即使中间重叠了 $[i,j]$ 这段区间也没有问题，重复算对 $\max$ 没有影响。
此外，我说一下复杂度问题：
- 时间复杂度：合并（建立）为 $\Theta(n \log n)$，查询为 $\Theta(1)$。
- 空间复杂度：$\Theta(n \log n)$，开销基本在 `st[][]` 数组上。
----------
### 3. 代码实现
我觉得上面解析的很明白了，代码注释就不加了。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
const int maxm = log2(maxn) + 10;
int n, q, a[maxn], st[maxn][maxm];
namespace quick {
inline int read() {
int x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
}
void st_build() {
for (int i = 1; i <= n; i++) st[i][0] = a[i];
int t = log2(n);
for (int j = 1; j <= t; j++)
for (int i = 1; i <= n - (1 << j) + 1; i++)
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
int st_query(int l, int r) {
int k = log2(r - l + 1);
return max(st[l][k], st[r - (1 << k) + 1][k]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
n = quick::read();
q = quick::read();
for (int i = 1; i <= n; i++) a[i] = quick::read();
st_build();
while (q--) {
int l = quick::read(), r = quick::read();
cout << st_query(l, r) << "\n";
}
return 0;
}
```
这里为了以防万一，还是按照题目的建议加了快读。
----------
### 4. 其他方法
对付 RMQ 问题，其实还有一种复杂的方法，就是普通线段树。更多请见 [这里](https://www.luogu.com.cn/problem/P3372) 哦，但线段树去解决 RMQ 问题其实小题大做了。值得说的是，线段树的查询操作是 $\Theta(\log n)$ 的，而不是 $\Theta(1)$ 的。代码贴在这里（根本不用 lazytag 的）：
```cpp
#include <bits/stdc++.h>
using namespace std;
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#define lson (p << 1)
#define rson (p << 1 | 1)
constexpr int maxn = 1e5 + 10;
int n, q, a[maxn];
struct node { int l, r, ans; } t[maxn << 2];
namespace quick {
inline int read() {
int x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
inline void w(int x) {
if (x < 0) { x = ~(x - 1); putchar('-'); }
if (x > 9) w(x / 10); putchar(x % 10 + '0');
}
}
inline void build(int p, int l, int r) {
t[p].l = l; t[p].r = r;
if (l == r) {
t[p].ans = a[l];
return;
}
int mid = (t[p].l + t[p].r) >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
t[p].ans = max(t[lson].ans, t[rson].ans);
}
inline int query(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r) return t[p].ans;
int mid = (t[p].l + t[p].r) >> 1, ans = 0;
if (l <= mid) ans = max(query(lson, l, r), ans);
if (r >= mid + 1) ans = max(query(rson, l, r), ans);
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
n = quick::read(), q = quick::read();
for (int i = 1; i <= n; i++) a[i] = quick::read();
build(1, 1, n);
while (q--) {
int l = quick::read(), r = quick::read();
quick::w(query(1, l, r)); putchar('\n');
}
return 0;
}
```
我在文章中讲解我一开始以为稀疏表查询时按二进制拆成若干个小区间的做法，其实在求区间加和、乘积等不能进行重叠计算的操作中可以使用。发展成这样的稀疏表已经很接近普通线段树了。
----------
谢谢大家的阅读！