ST表(Sparse-Table 算法)

本文主要是介绍ST表(Sparse-Table 算法)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

引入 (RMQ问题)

RMQ (Range Minimum/Maximum Query):询问区间内的最小/最大值

具体要求:

出一个 \(n\) 个元素的数组 \(A1 ,A2 , …, An\), 设计一个数据结构, 支持查询操作 \(query(L, R)\), 计算 \(min(A_L, A_{L+1}, ..., A_R)\), \(max(A_L, A_{L+1}, …, A_R)\)

ST表(Sparse-Table 算法)

我们将先把问题以图的方式画出来, 以下

触控板用的不是很熟所以不是很好看(

思路

• 对于 \(A\) 数组中的每一个位置 \(i\), 我们可以算出 \(min(A_i, ..., A_{i+2^{j-1}}-1)\) (max同, 后同), 即可令 \(d[i][j]\) 长度为 \(2^j\) 的元素中的最小值, 则有 \(d[i][j] = min(d[i][j-1], d[i+2^{j-1}][j-1])\), \(d[i][0] = a[i]\).

• 对于 \(query(L,R)\), 我们只需要求 \(min(d[L][k], d[R-2^k+1][k])\)即可.

模板

#include <stdio.h>
#include <iostream>
using namespace std;

int n, m, a[100003];
int d[100003][103];

inline void init() {		// 初始化
	for (int i = 1; i <= n; i++)
		d[i][0] = a[i];
	for (int j = 1; (1 << j) <= n; j++)
		for (int i = 1; i + (1 << j) - 1 <= n; i++)		// 注意不能使 i + (1 << j) - 1, 即 d[i][j] 所对应区间的右端点超过 n
			d[i][j] = min(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
	return;
} 

inline int quety(int L, int R) {		//查询操作
	int k = 0;
	while ((1 << (k + 1)) <= R - L + 1)
		k++;
	return min(d[L][k], d[R - (1 << k) + 1][k]);
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	init(); 
	for (int i = 1; i <= m; i++) {
		int L, R;
		scanf("%d %d", &L, &R);
		printf("%d\n", quety(L, R));
	}
	return 0;
}

洛谷的 P3865 【模板】ST 表 与我的代码只有 min 和 max 之差, 可以练习.

• 有关\(query(int L, int R)\)函数的解释.

先给出一个简单例子

我字好丑::>_<::

可以发现上图中的节点个数为 8, 答案即为 \(d[L][3]\).

然后是一个复杂例子

可以发现, 这张图与上张图对比, 多了一个节点, 节点数不再是 \(2^p\) 的形式, \(d[L][3]\)这个答案并不能覆盖整个区间.

于是可以想到, 能否用两个较大的, 重合的区间覆盖整个区间, 如图中已经画上的黑色波浪和红色波浪, 前者最小值是 \(d[L][3]\), 后者最小值是\(d[L+1][3]\), 即\(d[R-2^3+1][3]\), 整个区间的最小值就是黑色波浪的最小值和红色波浪的最小值中的小者, 即\(min(d[L][3], d[R-2^3+1][3])\), 并令一值 k.在 k 取值正确的情况下, \(query(L,R) = min(d[L][k], d[R-2^k+1][k])\).

不难发现, 想要使得两个区间的并集等于区间[L, R], 仅需使得 \(2^k <= R-L+1 < 2^{k+1}\)成立即可.

于是就完成了有关\(query(int L, int R)\)函数的解释.

例题

UVA11235 Frequent values

不是很难, 但是坑点较多.

思路

写的好丑..

一些易错点

• 忘记置零

• 没有进行分类讨论

• 各种地方的 +1, -1 忘记打

• 其他的一些永远也想不到的错误

程序如下

#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
int m, n = 0, l[100003], r[100003], id[100003];
int d[100003][103];
inline void init() {
	for (int i = 1; i <= n; i++)
		d[i][0] = r[i] - l[i] + 1;
	for (int j = 1; (1 << j) <= n; j++)
		for (int i = 1; i + (1 << j) - 1 <= m; i++)
			d[i][j] = max(d[i][j-1], d[i+(1<<(j-1))][j-1]);
	return;
}
inline int query(int L, int R) {
	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 q;
	while (~scanf("%d", &m) && m) {
		n = 0;
		memset(l, 0, sizeof(l));
		memset(r, 0, sizeof(r));
		memset(id, 0, sizeof(id));
		memset(d, 0, sizeof(d));
		scanf("%d", &q);
		int last = -100003;
		for (int i = 1; i <= m; i++) {
			int x;
			scanf("%d", &x);
			if (x != last)
				r[n] = i-1, l[++n] = i, last = x;
			id[i] = n;
		}
		init();
		while (q--) {
			int L, R;
			scanf("%d %d", &L, &R);
			if (id[L] == id[R])		// 只能分成一部分 
				printf("%d\n", R - L + 1);
			else if (id[L] + 2 <= id[R]) 		// 可以分成三部分
				printf("%d\n", max(query(id[L] + 1, id[R] - 1), max(r[id[L]] - L + 1, R - l[id[R]] + 1)));
			else		// 只能分成两部分 
				printf("%d\n", max(r[id[L]] - L + 1, R - l[id[R]] + 1));
		}
	}
	return 0;
}

这篇关于ST表(Sparse-Table 算法)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！