Home ST表
Post
Cancel

ST表

ST(Sparse Table)表,中文名稀疏表,是一种数据结构。

ST表常用于解决可重复贡献问题.

不知道什么是「可重复贡献问题」? 一句话解释, 就是: 对于运算 op, 有 x op x = x. 想要详细了解可以去查一查.

常见的可重复贡献问题有: 区间最值、区间按位和、区间按位或、区间 GCD 等. 而像区间和这样的问题就不是可重复贡献问题.

P3865 【模板】ST 表

Link

这是一道 ST 表经典题——静态区间最大值.

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

考虑暴力做法, 每次都对区间 [l,r] 扫描一遍, 求出最大值, 显然会超时.

ST 表基于倍增思想, 预处理部分可以达到 $O(n\log{n})$ 的时间复杂度, 但是不支持修改.

预处理部分的过程通常是: 对于 n 个数, 构造记录状态的数组 (通常是二维的, 例如 m*n), 然后像动态规划那样计算出每个状态. 由于这里利用了「倍增」的思想, 所以那个 m 就应该等于 $\log{n}$.

先看看什么是倍增.

倍增思想

引入一个利用倍增思想的例题:

一个长度为 n 的环, 每次从第 i 个点跳到第 (i+k)%n+1 个点, 总共跳 m 次. 每个点都有一个权值, 要求出跳 m 次后经历的所有起点的权值的和 (对一个数取模后的结果).

go[i][x] 表示第 x 个点跳 $2^i$ 步之后的终点, sum[i][x] 表示第 x 个点跳 $2^i$ 步之后能获得的点权和.

代码同样来自 OI wiki.

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
using namespace std;

const int mod = 1000000007;

int modadd(int a, int b) {
  if (a + b >= mod) return a + b - mod;  // 减法代替取模,加快运算
  return a + b;
}

int vi[1000005];

int go[75][1000005];  // 将数组稍微开大以避免越界,小的一维尽量定义在前面
int sum[75][1000005];

int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", vi + i);
  }

  for (int i = 1; i <= n; ++i) {  // 从第 i 个结点跳 1 步
    go[0][i] = (i + k) % n + 1;
    sum[0][i] = vi[i];
  }

  int logn = 31 - __builtin_clz(n);  // 一个快捷的取对数的方法
  for (int i = 1; i <= logn; ++i) {
    for (int j = 1; j <= n; ++j) {
      go[i][j] = go[i - 1][go[i - 1][j]];
      sum[i][j] = modadd(sum[i - 1][j], sum[i - 1][go[i - 1][j]]);
    }
  }

  long long m;
  scanf("%lld", &m);

  int ans = 0;
  int curx = 1;
  for (int i = 0; m; ++i) {
    if (m & (1 << i)) {  // 参见位运算的相关内容,意为 m 的第 i 位是否为 1
      ans = modadd(ans, sum[i][curx]);
      curx = go[i][curx];
      m ^= 1ll << i;  // 将第 i 位置零
    }
  }

  printf("%d\n", ans);
}

回到正题

如果按照一般的倍增流程, 每次跳 $2^i$ 步的话, 询问时的复杂度仍旧是 $\log{n}$ (因为需要将查询区间分解为预处理的多个子区间才能使用预处理的结果), 并没有比线段树更优, 反而还会因为预处理部分而比线段树慢.

但是! 这是一个「可重贡献问题」. 也就是说, 我们其实不必将 k 精确地分解, 而是只要能够快速找到几个预处理区间使得它们的并集能够覆盖查询区间就可以了. 意思是说, [l,r] 的最大值不仅等于 max(max{[l,k],[k+1,r]}), 也等于 max(max{[l,k2],[k1,r]}), k1<=k2.

具体做法

预处理:

  • 我们令 f(i,j) 表示区间 $[i,i+2^j-1]$ 的最大值, 也就是说这个区间的确定方式是由 i 以及从 i 跳 $2^j-1$ 步到达的点所确定的区间.
  • 初始状态: f(i,0)=a[i], 即从 i 跳 0 步到达的点的权值是 a[i]. 因为就是自己.
  • 怎么写出状态转移方程呢? 将区间 $[i,i+2^j-1]$ 分为两部分: $[i,i+2^{j-1}-1]$ 和 $[i+2^{j-1},i+2^j-1]$. 注意到 $i+2^j-1=(i+2^{j-1})+2^{j-1}-1$, 那么这两个子区间分别对应的状态函数就是 f(i,j-1)f(i+2^{j-1},j-1).
  • 这就可以很容易地写出状态转移方程了: $f(i,j) = max(f(i,j-1), f(i+2^{j-1},j-1))$.

查询:

  • 对于每个询问 [l,r], 我们将它分为两部分: $[l,l+(2^k-1)]$ 和 $[r-(2^k-1),r]$. 根据 $l+(2^k-1)==r$ 或者 $r-(2^k-1)==l$, 可以算出 $k=\lfloor\log{r-l+1}\rfloor$. 两部分的结果的最大值就是回答.
  • 根据 $l+(2^k-1)==r$ 或者 $r-(2^k-1)==l$ 算出 k 是为了保证区间 [l,r] 被完全覆盖, 宁可有重叠也不能让中间的一部分区间被遗漏.
  • 能用 $l+(2^k-1)+1==r-(2^k-1)$ 吗? 首先, 这个对数值算出来很大概率是一个浮点数, 不可能达到完全精确, 那么我们怎么去取 k 的值? 如果给 k 向下取整, 那么左边子区间的右端点会变小, 右边子区间的左端点会变大, 中间就可能会遗漏一小部分没有被覆盖; 如果给 k 向上取整, 那么左边子区间的右端点会变大, 右边子区间的左端点会变小, 这种做法其实也是可以的.

贴上我自己的代码:

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
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100010
int n,m,l,r,k;
int a[N],f[20][N]; //log(100000)=16
inline int clz(int x){
    return 31-__builtin_clz(x);
}
inline int read(){
    char ch=getchar();
    int x=0,f=1;
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void Init(){
    for(int i=1;i<=n;++i)
        f[0][i]=a[i];
    int logn=clz(n);
    //O(nlogn)
    for(int i=1;i<=logn;++i)
        for(int j=1;j<=n;++j)
            f[i][j]=max(f[i-1][j],f[i-1][j+(1<<(i-1))]);
}
int main() {
    n=read(),m=read();
    for(int i=1;i<=n;++i) a[i]=read();
    Init();
    while(m--){
        l=read(),r=read();
        k=clz(r-l+1);
        //如果是第二种方法,k就要上取整,这里直接+1
        //k=clz((r-l+1)>>1)+1;
        printf("%d\n", max(f[k][l],f[k][r-(1<<k)+1]));
    }
    return 0;
}

注意那个 logn 打表算亦可, 但是我这样更简单 :D

This post is licensed under CC BY 4.0 by the author.