ST表

  • 时间:
  • 来源:互联网
  • 文章标签:

ST表(sparse-table)是一种代码极其短的数据结构,RMQ(Range Minimum Qustion,范围最小值问题)专用。

RMQ就是给你一个序列不断询问你给定区间内的最小值。

ST表只能解决静态的RMQ,动态的需要用到万能的常数贼大的线段树。

链接

ST表基本思想: d [ i ] [ j ] d[i][j] d[i][j] 表示以 i i i 为起点,长度为 2 j 2^j 2j 这一段区间中的最小值。

例如, d [ 3 ] [ 2 ] d[3][2] d[3][2] 就是 3 ∼ 3 + 2 2 3\sim 3+2^2 33+22 区间,即 3 ∼ 7 3\sim 7 37 区间的最小值。

ST表初始化代码:

for (register int i(1); i <= n; ++ i) d[i][0] = a[i] = read();
for (register int i(n); i >= 1; -- i)
for (register int j(1); i + (1 << j - 1) <= n; ++ j)
d[i][j] = max(d[i][j - 1], d[i + (1 << j - 1)][j - 1]);

由于本身ST表解决问题范围有很大的局限性上述代码可以直接背。

原理用一张图就可以说明了:

在这里插入图片描述
我们要算出 d [ i ] [ j ] d[i][j] d[i][j] 的值,也就是 i ∼ i + 2 j i\sim i+2^j ii+2j 区间内的最小/大值,此时可以将它分成两部分: i ∼ i + 2 j − 1 i\sim i+2^{j-1} ii+2j1 i + 2 j − 1 i+2^{j-1} i+2j1。在这两个区间里取最小/大值即可。

查询操作: 设我们要查询 [ L , R ) [L,R) [L,R) 区间的最小/大值,设 2 k < R − L < 2 k + 1 2^k<R-L<2^{k+1} 2k<RL<2k+1,则可以通过区间 [ L , L + 2 k ) [L,L+2^k) [L,L+2k) 与区间 [ R − 2 k + 1 , R ) [R-2^k+1,R) [R2k+1,R) 的解合并得到。如图。

在这里插入图片描述

其实我们算重了一段区间: [ R − 2 k + 1 , L + 2 k − 1 ) [R-2^k+1,L+2^k-1) [R2k+1,L+2k1),不过对于取最值无所谓。正因为如此,ST表无法处理加法的情况。(不过我奶出来了一个ST表求区间加法的方法,后面说)。

查询操作代码:

inline int query(int L, int R) {
	register int k(0);
	while ((1 << k + 1) <= R - L + 1) ++ k;
	return max(d[L][k], d[R - (1 << k) + 1][k]);
}

ST表预处理复杂度 O ( n l o g n ) O(nlogn) O(nlogn),查询操作……别人都说 O ( 1 ) O(1) O(1),可是蒟蒻觉得是 O ( l o g n ) O(logn) O(logn) 啊?

完整代码:(后面才是重头戏,这个代码只是铺垫一下)

#include <cstdio>
#define max(x, y) (x > y ? x : y)
#define nc (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 65536, stdin), p1 == p2) ? EOF : * p1 ++)

char buf[65536], * p1, * p2;

inline int read() {
	int x(0);
	char ch;
	while ((ch = nc) < 48);
	while (ch >= 48) x = x * 10 + ch - 48, ch = nc;
	return x;
}

int d[100005][20], a[100005];

inline int query(int L, int R) {
	register int k(0);
	while ((1 << k + 1) <= R - L + 1) ++ k;
	return max(d[L][k], d[R - (1 << k) + 1][k]);
}

int main() {
	int n(read()), m(read());
	for (register int i(1); i <= n; ++ i) d[i][0] = a[i] = read();
	for (register int i(n); i >= 1; -- i)
	for (register int j(1); i + (1 << j - 1) <= n; ++ j)
	d[i][j] = max(d[i][j - 1], d[i + (1 << j - 1)][j - 1]);
	while (m --) {
		register int L(read()), R(read());
		printf("%d\n", query(L, R));
	}
}

下面是我奶出的静态区间求和ST表实现法:

预处理阶段将 m a x max max 改为求和即可。查询操作我采用了递归计算:上面有说到,查询操作重复计算了一部分,那我们将这一坨减去不就可以了?预处理复杂度不变,但是查询操作大概率会被卡掉……所以我们采取了一种新的方法:

先计算区间 [ L , L + 2 k − 1 ) [L,L+2^k-1) [L,L+2k1) 的和,然后递归计算区间 [ L + 2 k , R ) [L+2^k, R) [L+2k,R) 的和。时间复杂度不变,只是常数飞起

C o d e : Code: Code:

#include <cstdio>
#define max(x, y) (x > y ? x : y)

char buf[65536], * p1, * p2;

inline int read() {
	int x(0), f(1);
	char ch;
	while ((ch = getchar()) < 48) if (ch == '-') f = -1;
	while (ch >= 48) x = x * 10 + ch - 48, ch = getchar();
	return x * f;
}

int d[100005][20], a[100005];

inline int query(int L, int R) {
	if (L > R) return 0;
	if (L == R) return a[L];
	register int k(0);
	while ((1 << k + 1) <= R - L + 1) ++ k;
	return d[L][k] + query(L + (1 << k), R);
}

int main() {
	int n(read()), m(read());
	for (register int i(1); i <= n; ++ i) d[i][0] = a[i] = read();
	for (register int i(n); i >= 1; -- i)
	for (register int j(1); i + (1 << j - 1) <= n; ++ j)
	d[i][j] = d[i][j - 1] + d[i + (1 << j - 1)][j - 1];
	while (m --) {
		register int L(read()), R(read());
		printf("%d\n", query(L, R));
	}
}

本文链接http://www.taodudu.cc/news/show-1781797.html