1. RMQ 是啥

RMQ (Range Minimum / Maximum Query)问题是指:对于长度为 $n$ 的数列 $A$,回答若干询问 $\text{RMQ}(A,i,j)(1\leq i,j\leq n)$,返回数列 $A$ 中下标在 $[i,j]$ 里的最小(大)值,也就是说,RMQ 问题是指求区间最值的问题。

全是抄的。

也就是说,RMQ 是一类问题,而不是一类数据结构。

所以暴力(没有初始化,查询$\Theta(n)$),线段树(初始化和查询都是 $\Theta(\log n)$)等都可以解决 RMQ 问题。

那么是否有更♂快的方法呢?

有!就是 ST 表


2. 概念

ST 表通过 DP 的方式,可以实现 $\Theta(n\log n)$ 初始化,$\Theta(1)$ 查询区间最值。

优点:最重要的,快!

缺点:不支持修改数组,而且空间复杂度为 $\Theta(n\log n)$,可能会受不了。


3. 实现

$dp_{i,j}$ 代表从 $i$ 开始,区间长度为 $2^j$ 的区间,即 $[i,i+2^j)$ 的最值(可以是最大值或者最小值,这个无所谓)。

初始化

对于 $\forall i,j=0$ 时,区间只有 $A_i$ 这一个数字,所以肯定最值是 $A_i$。

状态转移

我们知道,对于任意一个长度为 $2$ 的幂次方的区间,都可以划分为长度相等的两部分,例如 $[3,10]$ 就像这样:

($i=3,j=3$)

也可以说明区间 $[i,i+2^j)$ 可以被分为 $[i,i+2^{j-1})$ 和 $[i+2^{j-1},i+2^j)$ 两个部分,每个部分的长度都是 $2^{j-1}$。

那么转移方程不就出来了吗:

当然,在代码的实现过程中,我们可以用 1 << x 来代替分析中的 $2^x$,不过需要注意的是,位运算的优先级比四则运算低,需要打括号。

查询

对于任意一个区间 $[i,j]$,如何用已经初始化好的 ST 表求解最值呢?

看图:

我们可以把任意一个区间分解成这样两个长度为 $2$ 的幂次的区间,一个区间左端点为待求区间的左端点,另一个区间的右端点为待求区间的右端点,两个区间的长度为所有 $2$ 的幂次中小于 $j-i+1$ 的最大的那一个,转换一下就变成了可以用 $2$ 的幂次表示的 $2^{\lfloor\log_2(j-i+1)\rfloor}$。(PS:$2^{\log_2(x)}=x$)。

找到两个分解后的区间,求一下最值就行了。


数列区间最大值问题:

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
#include <cstdio>
#include <cmath>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)

const int maxn = (int)1e5 + 5;

int n, q, a[maxn], dp[maxn][1005];

inline int max(int x, int y) { return x > y ? x : y; }

inline void init() {
rep(i, 1, n)
dp[i][0] = a[i];
for(int j = 1; 1 << j <= n; ++j)
for(int i = 1; i + (1 << j - 1) - 1 <= n; ++i)
dp[i][j] = max(dp[i][j - 1], dp[i + (1 << j - 1)][j - 1]);
return;
}

inline int rmq(int l, int r) {
int k = log2(r - l + 1); // cmath 库中有内置的 log2 函数,请注意不要用成以 e 为底的 log 函数
return max(dp[l][k], dp[r - (1 << k) + 1][k]);
}

int main() {
scanf("%d %d", &n, &q);
rep(i, 1, n)
scanf("%d", &a[i]);
init();
int l, r;
rep(i, 1, q) {
scanf("%d %d", &l, &r);
printf("%d\n", rmq(l, r));
}
return 0;
}

4. 应用

ST 表本身就是个工具,我们在平时做题的时候不能想着刻意去使用它,详情参考洛谷 P2048

另外,ST 表之所以有局限性,是因为它在查询的时候可能会有一部分区间被重复查询,所以只能求解那些有重复元素不影响最终结果的问题。这种问题除了最大最小值之外,还有 gcd、lcm 等,所以这些问题也是可以通过 ST 表求的。