定义
ST 表（Sparse Table，稀疏表）是用于解决 可重复贡献问题 的数据结构。——OI Wiki
可重复贡献问题是什么我也不知道
作用
求静态区间最大（小）值，即一个区间不会修改。
能够实现 $\mathcal O(n\log_2 n)$ 预处理，$O(1)$ 查询。
实现
倍增思想
设 $\large f_{x,i}$ 表示区间 $[x,x+2^i-1]$ 的最大值。（最小值同理，下文不再赘述）
那么显然有：
\(\large f_{x,0}=a_x\)
不难发现，$[l,l+2^p]$ 的区间最大值是区间 $[l,l+2^{p-1}]$ 和区间 $[l+2^{p-1}+1,l+2^p]$ 的最大值。那么 $\large f_{x,i}$ 的转移方程就有（$i>0$）：
\(\large f_{x,i}=\max(f_{x,i-1},f_{x+2^{i-1},i-1})\)
其实和倍增LCA的转移方程很像虽然倍增算法基本都长这样，一同理解倍增可能会好一些。
预处理
设数组 $f[x][i]$，定义同 $f_{x,i}$。
那么预处理部分的代码就很简单了：
1
2
3
4
5
6
7
8
9
void st_pre(){
for(int i=0;i<=n;i++)lg[i]=lg[i/2]+1;//常数优化
for(int i=1;i<=n;i++)f[i][0]=a[i];
for(int i=1;i<=lg[n];i++){//循环顺序不能改！！
for(int x=1;x+(1<<i)-1<=n;x++){
f[x][i]=max(f[x][i-1],f[x+(1<<i-1)][i-1]);//状态转移方程
}
}
}
其中，$lg[i]$ 表示 $\log_2i+1$。
时间复杂度：$\mathcal O(n\log_2 n)$。
查询
ST表可以实现 $\mathcal O(1)$ 查询，实现如下：
询问区间 $[l,r]$ 时，我们只需要返回区间 $\large[l,s]$ 和区间 $\large[r-2^s+1,r]$ 的最大值即可，其中 $s=\lfloor \log_2(r-l+1)\rfloor$（区间长度的对数）。
其实这样分成的两个区间会有重复部分（一定覆盖了 $[l,r]$），但是并不影响我们求区间最大值。
查询代码也很简单：
1
2
3
4
int l,r;
scanf("%d %d",&l,&r);
int s=log2(r-l+1);
printf("%d\n",max(f[l][s],f[r-(1<<s)+1][s]));
例题
洛谷P3865
ST表模板题，虽然时限 $800ms$，但不加快读也能过。参考代码：
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
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
const int N=1e5;
int n,m,a[N+1],lg[N+1],f[N+1][(int)log2(N)+1];
void st_pre(){
for(int i=0;i<=n;i++)lg[i]=lg[i/2]+1;
for(int i=1;i<=n;i++)f[i][0]=a[i];
for(int i=1;i<=lg[n];i++){
for(int x=1;x+(1<<i)-1<=n;x++){
f[x][i]=max(f[x][i-1],f[x+(1<<i-1)][i-1]);
}
}
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",a+i);
st_pre();
while(m--){
int l,r;
scanf("%d %d",&l,&r);
int s=log2(r-l+1);
printf("%d\n",max(f[l][s],f[r-(1<<s)+1][s]));
}
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
