[算法]浅谈 ST 表
wangyibo201026
·
·
个人记录
\text{ST} 表是什么
它能够维护静态区间最值，并且时间复杂度是 $O(n\log n)$，常数极小，~~相比线段树，不知道好到哪里去了。~~
## 思想
$\text{ST}$ 表利用倍增的思想来求区间最值。
首先我们可以令 $f_{i, j}$ 表示从位置 $i$ 开始的后面一共 $2^j$ 个数的最大值，注意，这 $2^j$ 个数包括 $i$。
所以我们可以得出以下初始结论：$f_{i, 0}$。
那么我们就可以轻而易举的推出 $f_{i, j}$ 是由哪两个区间推出来的了。首先我们知道：$2^j = 2^{j - 1} \times 2^{j - 1}$，那么当前区间长为 $2^j$ 的区间就应该为两个长度为 $2^{j - 1}$ 的区间取 $\max$ 的来。这样思考，那么 $f_{i, j} = \max(f_{i, j - 1}, f_{i + 2^{j - 1}, j - 1})$。此时的 $i + 2^{j - 1}$ 就是第二个长度为 $2^{j - 1}$ 的区间的起始点。
这样来看，$ST$ 表的 $f$ 数组更类似与 $dp$ 的转移，而我们的 $j$ 是递减的，所以我们应该在第一层循环枚举 $j$，那么循环的边界就肯定是 $\log n$ 的。然后我们看对于 $i$ 的循环，对于 $i$ 的循环，应该有两个条件：
1. $i \le n$。
2. $j + 2^j - 1 \le n$。
这个式子我们是可以轻而易举的推出来的。但是，作者想说的是，虽然式子推出来了，但是式子里有许多 $2^j$ 和 $\log j$，所以我们可以用一个数组存下来，~~卡常数~~。
接下来是预处理代码：
```cpp
bin[0] = 1;
logg[0] = -1;
for(int i = 1; i <= 20; i++){
bin[i] = bin[i - 1] << 1;
}
for(int i = 1; i <= n; i++){
logg[i] = logg[i >> 1] + 1;
}
for(int i = 1; i <= logg[n]; i++){
for(int j = 1; j <= n && j + bin[i] - 1 <= n; j++){
f[j][i] = max(f[j][i - 1], f[j + bin[i - 1]][i - 1]);
}
}
```
这里并没有放上初始化 $f_{i, 0}$ 的代码。
然后我们如何查询呢？首先我们要知道一点：对于长度为 $x$ 的区间，设 $k = \log(x)$，则这段区间肯定可以被两端长度为 $2^k$ 的区间覆盖起来。
知道了这个结论，就很简单了吧！接下来直接放代码了：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;;
int n, m;
int f[N][21], logg[N], bin[21];
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-'){
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = x * 10 + ch - 48;
ch = getchar();
}
return x * f;
}
int main(){
n = read();
m = read();
for(int i = 1; i <= n; i++){
f[i][0] = read();
}
bin[0] = 1;
logg[0] = -1;
for(int i = 1; i <= 20; i++){
bin[i] = bin[i - 1] << 1;
}
for(int i = 1; i <= n; i++){
logg[i] = logg[i >> 1] + 1;
}
for(int i = 1; i <= logg[n]; i++){
for(int j = 1; j <= n && j + bin[i] - 1 <= n; j++){
f[j][i] = max(f[j][i - 1], f[j + bin[i - 1]][i - 1]);
}
}
for(int i = 1; i <= m; i++){
int x, y;
x = read();
y = read();
int len = y - x + 1, tmp = logg[len];
cout << max(f[x][tmp], f[y - bin[tmp] + 1][tmp]) << '\n';
}
return 0;
}
```