LogoCSP Wiki By Yundou
3 DS

ST表

定义

ST 表(Sparse Table,稀疏表)是用于解决 可重复贡献问题 的数据结构。

图片描述

什么是可重复贡献问题?

可重复贡献问题 是指对于运算 opt\operatorname{opt},满足 xoptx=xx\operatorname{opt} x=x,则对应的区间询问就是一个可重复贡献问题。例如,最大值有 max(x,x)=x\max(x,x)=x,gcd 有 gcd(x,x)=x\operatorname{gcd}(x,x)=x,所以 RMQ 和区间 GCD 就是一个可重复贡献问题。像区间和就不具有这个性质,如果求区间和的时候采用的预处理区间重叠了,则会导致重叠部分被计算两次,这是我们所不愿意看到的。另外,opt\operatorname{opt} 还必须满足结合律才能使用 ST 表求解。

什么是 RMQ?

RMQ 是英文 Range Maximum/Minimum Query 的缩写,表示区间最大(最小)值。解决 RMQ 问题有很多种方法,可以参考 RMQ 专题

引入

ST 表模板题

题目大意:给定 nn 个数,有 mm 个询问,对于每个询问,你需要回答区间 [l,r][l,r] 中的最大值。

考虑暴力做法。每次都对区间 [l,r][l,r] 扫描一遍,求出最大值。

显然,这个算法会超时。

ST 表

ST 表基于倍增思想,可以做到 Θ(nlogn)\Theta(n\log n) 预处理,Θ(1)\Theta(1) 回答每个询问。但是不支持修改操作。

基于倍增思想,我们考虑如何求出区间最大值。可以发现,如果按照一般的倍增流程,每次跳 2i2^i 步的话,询问时的复杂度仍旧是 Θ(logn)\Theta(\log n),并没有比线段树更优,反而预处理一步还比线段树慢。

我们发现 max(x,x)=x\max(x,x)=x,也就是说,区间最大值是一个具有「可重复贡献」性质的问题。即使用来求解的预处理区间有重叠部分,只要这些区间的并是所求的区间,最终计算出的答案就是正确的。

如果手动模拟一下,可以发现我们能使用至多两个预处理过的区间来覆盖询问区间,也就是说询问时的时间复杂度可以被降至 Θ(1)\Theta(1),在处理有大量询问的题目时十分有效。

具体实现如下:

f(i,j)f(i,j) 表示区间 [i,i+2j1][i,i+2^j-1] 的最大值。

显然 f(i,0)=aif(i,0)=a_i

根据定义式,第二维就相当于倍增的时候「跳了 2j12^j-1 步」,依据倍增的思路,写出状态转移方程:f(i,j)=max(f(i,j1),f(i+2j1,j1))f(i,j)=\max(f(i,j-1),f(i+2^{j-1},j-1))

图片描述

以上就是预处理部分。而对于查询,可以简单实现如下:

对于每个询问 [l,r][l,r],我们把它分成两部分:[l,l+2s1][l,l+2^s-1][r2s+1,r][r-2^s+1,r],其中 s=log2(rl+1)s=\left\lfloor\log_2(r-l+1)\right\rfloor。两部分的结果的最大值就是回答。

图片描述

根据上面对于「可重复贡献问题」的论证,由于最大值是「可重复贡献问题」,重叠并不会对区间最大值产生影响。又因为这两个区间完全覆盖了 [l,r][l,r],可以保证答案的正确性。

示例代码

#include <algorithm>
#include <iostream>
using namespace std;
constexpr int MAXN = 2000001;
constexpr int logN = 21;
int f[MAXN][logN + 1], Logn[MAXN + 1];
 
void pre() {  // 准备工作,初始化
  Logn[1] = 0;
  Logn[2] = 1;
  for (int i = 3; i < MAXN; i++) {
    Logn[i] = Logn[i / 2] + 1;
  }
}
 
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> f[i][0];
  pre();
  for (int j = 1; j <= logN; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);  // ST表具体实现
  for (int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    int s = Logn[y - x + 1];
    cout << max(f[x][s], f[y - (1 << s) + 1][s]) << '\n';
  }
  return 0;
}

注意点

  1. 输入输出数据一般很多,建议开启输入输出优化。

  2. 每次用库自带的log函数重新计算 log 函数值并不值得,建议进行如下的预处理:

{Logn[1]0,Logn[i]Logn[i2]+1.\begin{cases} \texttt{Logn}[1] \gets 0, \\ \texttt{Logn}\left[i\right] \gets \texttt{Logn}\left[\frac{i}{2}\right] + 1. \end{cases}

ST 表维护其他信息

除 RMQ 以外,还有其它的「可重复贡献问题」。例如「区间按位与」、「区间按位或」、「区间 GCD」,ST 表都能高效地解决。

需要注意的是,对于「区间 GCD」,ST 表的查询复杂度并没有比线段树更优(令值域为 ww,ST 表的查询复杂度为 Θ(logw)\Theta(\log w),而线段树为 Θ(logn+logw)\Theta(\log n+\log w),且值域一般是大于 nn 的),但是 ST 表的预处理复杂度也没有比线段树更劣,而编程复杂度方面 ST 表比线段树简单很多。

如果分析一下,「可重复贡献问题」一般都带有某种类似 RMQ 的成分。例如「区间按位与」就是每一位取最小值,而「区间 GCD」则是每一个质因数的指数取最小值。

总结

ST 表能较好的维护「可重复贡献」的区间信息(同时也应满足结合律),时间复杂度较低,代码量相对其他算法很小。但是,ST 表能维护的信息非常有限,不能较好地扩展,并且不支持修改操作。

例题:

On this page