Junie's Blog

ST 表（Sparse Table）入门

全文共 626 字预计阅读 3 分钟

ST表（Sparse Table 稀疏表）

用处：

可以用来解决RMQ（区间最值）等可重复贡献问题1。

引入：

对于RMQ问题，我们通常有这几种方法处理：

  1. 朴素（即搜索）O(nm)O(nm)

  2. 打表 O(n2)O(n^2)

  3. ST表 O(nlogn)O(nlogn)

  4. 线段树 O(nlogn)O(nlogn)

我们比较容易想到用打表的方法，也就是比较简单的dp，像这样： 定义 ans[i][j]ans[i][j] 表示区间 [i,j][i,j] 的最值 {ans[i][j]=a[i],i=jans[i][j]=max(ans[i][j−1],a[j])\begin{cases} ans[i][j] = a[i] , i = j\\\\ ans[i][j] = max(ans[i][j-1], a[j]) \end{cases}

可是这样的空间复杂度 O(n2)O(n^2) 时间复杂度 O(n2)O(n^2) 不是很令人满意，所以我们考虑用ST表来处理静态(offline)\mathrm{(offline)}的RMQ问题。

分析：

要求解一个区间的最值，ST表用了类似区间dp的方法。 dp[i][j]dp[i][j] 表示的是从 ii 开始，长度为 2j2^j 的区间中的最值。也就是区间 [i,2j+i−1][i,2^j+i-1] 的最值。

对于每一次询问，我们可以通过 ll 和 rr 算得区间的长度 lenlen ，然后计算 j=⌊log2len⌋j = \lfloor log_{2}{len} \rfloor 最大值就是 max(dp[l][j],dp[r−2j+1][j])max(dp[l][j], dp[r-2^j+1][j]) 就像这样： 就是在这两段有重叠部分的区间取其中的最大值，重叠并不会影响 [l,r][l,r] 区间的最大值。

预处理：

首先，当区间长度为0时，区间的最值就是区间端点的值。即 dp[i][0]=a[i]dp[i][0] = a[i]

然后开始类似区间dp的处理方法。

先枚举区间长度，再枚举区间端点。

dp[i][j]=max(dp[i][j−1],dp[i+2j−1][j−1])dp[i][j] = max(dp[i][j-1], dp[i+2^{j-1}][j-1])

这里的 j−1j-1 相当于将区间对半分，整个的最值等于左边和右边取最值。 代码：

for (int j = 1; j <= log2(n); j++)
    for (int i = 0; i + (1 << j) - 1 < n; i++)
        dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);

查询：

和分析中说的一样 代码：

int query(int l, int r)
{
    int j = (int)log2(r - l + 1);
    return max(dp[l][j], dp[r - (1 << j) + 1][j]);
}

例题：

模板代码：

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int n, m, a[100010], f[100010][20];
int log2(int x) {
	int cnt = -1;
	while (x) x >>= 1, cnt++;
	return cnt;
}
void prework() {
	for (int i=1;i<=n;i++) f[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++)
			f[i][j] = max(f[i][j-1], f[i+(1<<(j-1))][j-1]);
}
int query(int l, int r) {
	int k = log2(r-l+1);
	return max(f[l][k], f[r-(1<<k)+1][k]);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i=1;i<=n;i++) cin >> a[i];
	prework();
	for (int i=0;i<m;i++) {
		int x,y;
		cin >> x >> y;
		cout << query(x,y) << '\n';
	}
}

Footnotes

  1. 可重复贡献问题我们要查询一块区域 AA 内的元素性质, 可以将该区域 用两块区域 BB CC 来替代(这两个区域, 可以包含相同元素,但不可以 包含不属于 AA 的元素) 即: B∪C=A,B∩C∈AB \cup C = A, B \cap C \in A 通过这个两个子区域的值, 可以推出 AA 的值。 换句话说, 假如我们要求的值 函数为: F(S)F(S) (表示 SS 这个集合里所有元素的结果)那么必须要满足: F(a,b,c,d)=F(F(a,b,c),F(b,c,d))F({a,b,c,d})=F(F({a,b,c}),F({b,c,d})) 比如：RMQRMQ 问题、区间 GCDGCD 、区间&操作、区间|操作等。 ↩

评论