数据结构-ST表

ST表

参考资料：ST 表 - OI Wiki

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

什么是可重复贡献问题?

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

什么是RMQ? RMQ是英文 Range Maximujm/Minimum Query的缩写,表示区间最大(最小值)。
## 引入

我们给定 \(n\) 个数, 有 \(m\) 个询问，对于每个询问，你需要回答区间 \([l,r]\) 中的最大值。

​ 如果考虑暴力做法。每次都对区间 \([l,r]\) 扫描一遍，求出最大值的话，由于每次查询为 \(O(n)\) ，当 \(m\) 个询问足够大时，时间开销会很大。

ST表

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

对于支持修改操作的问题，线段树可以做到，详见数据结构-线段树 | 4FGR の Blog

我们以求区间最大值为例, 我们发现存在 \(\max(x,x)=x\) , 显然区间最大值是符合可重复贡献问题的性质。我们会对区间进行预处理，而预处理区间会有重叠部分，只要这些区间的并(union)是所求的区间，最终计算出的答案就是正确的。

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

具体实现如下：

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

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

这样的定义是怎么来的呢？第二维就相当于倍增的时候跳了 \(2^i-1\) 步，我们可根据倍增的思路写出状态转移方程。

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

即，对于区间 \([i,i+2^{j-1}-1]\) 和 \([i+2^{j-1},i+2^{j-1}-1]\) 的最大值，显然就是区间 \([i,i+2^{j}-1]\) 的最大值

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

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

由于 \(s\geq 0\) 能保证 \((l+2^s-1)-(r-2^s+1)=2(2^s-1)-(r-l+1)+1 \geq 2(2^s-1)-2^s+1 \geq 0\)

当且仅仅当 \(l=r\) 时使得差值为 \(0\)

因此保证两区间一定能完整表示区间 \([l,r]\)

显然区间右边得表示成 \(i+2^s-1\) 的形式，在程序中，为

\(max(f[l][s],f[r-(1<<j)+1][s])\)

实现代码

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
#include<bits/stdc++.h>

using namespace std;
const int N =1e5+10;
int st[N][20];

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> st[i][0];
    }
    int li = log2(n);
    for(int j=1;j<=li;j++){
        for(int i=0;i+(1<<j)-1<=n;i++){
            st[i][j] = max(st[i][j-1],st[i+(1<<j-1)][j-1]);
        }
    }
    while(m--){
        int l,r;
        cin >> l >> r;
        cout << query(l,r) << '\n';
    }
}