ST表

发表于

ST 表是一个在 O(nlogn) 时间复杂度预处理后在允许在 O(1) 的时间内查询区间最大最小值的，额，方法，或数据结构。一个非常神奇的算法。

预处理部分

我们需要预处理一个 $st$ 数组，$st[i][j]$ 则代表序列第 $i$ 位开始向后 $2^j$ 位的最大值。

这个预处理我们很显然可以用动态规划来做(以最大值查询为例，最小值只需要把 $\max$ 改为 $\min$ 即可)。

即 $st[i][j] = \max(st[i][j - 1]， st[i + 2^{k - 1}][k - 1])$，即区间 $[i, i + 2^j]$ 的最大值为区间 $[i, i + 2^{j - 1}]$ 的最大值和区间 $[i + 2^{j - 1}, i + 2^j]$ 的最大值的最大值。

如此即可在 O(nlogn) 时间复杂度内预处理。

查询部分

预处理的方程给了我们一些启发，我们可以用合并两个区间最大但是值的方式来处理出一个更大区间的最大值，如我们需要查询区间 $[1, 10]$ 中的最大值，很显然如果我们知道 $[1, 5]$ 的最大值和 $[6, 10]$ 的最大值我们可以直接求。但有些时候我们并没有区间 $[1, 5]$ 或区间 $[6, 10]$ 的最大值，所以我们可以让区间 $[1, 8]$ 和区间 $[3, 10]$ 合并(即取两个区间最大值的最大值)，这样我们仍可求出区间 $[1, 10]$ 的最大值。

如此我们推广到任意区间 $[a, b]$，我们取 $c = \log_2(b - a + 1)$，即其最大值便为 $\max(st[a][c], st[a - 2^b + 1][c])$，对于 2 的幂我们可以用 $2^i = 1 << i$ 来计算。

另外很多地方说不推荐使用库函数的 $\log$ 函数，推荐先预处理出来，但是库函数包括 sqrt, log, sin, cos 等效率还是很高的，而且随着参数增大所用时间几乎不变，相较于几个大数相乘还是要快一些的。所以我这里就用了库函数：

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
#include <cstdio>
#include <cmath>
#include <algorithm>
#define MAX(a, b)	((a) > (b) ? (a) : (b))
#define MAXN 10000

int st_seque[MAXN][14];

inline void init(){
	int c = log2(MAXN);
	for(int k = 1; k < c; k++)
		for(int j = 0; j + (1 << k - 1) < MAXN; j++)
			st_seque[j][k] = MAX(st_seque[j][k - 1], st_seque[j + (1 << k - 1)][k - 1]);
}

inline int Query(int a, int b){
	int c = log2(b - a + 1);
	return MAX(st_seque[a][c], st_seque[b - (1 << c) + 1][c]);
}

int main(int argc, char *argv[]){
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
		scanf("%d", &st_seque[i][0]);
	init();
	scanf("%d", &n);
	while(n--){
		int a, b;
		scanf("%d%d", &a, &b);
		printf("%d\n", Query(a, b));
	}
	return 0;
}