重学ST表
ST表能做什么?
- 预处理并 $O(1)$ 求出区间最大/最小值(也就是 RMQ, Range Maximum/Minimum Query )。
- 区间 GCD 问题。
- 区间按位和/或。
而以上这些,都有一个特性:一个值对于好几段包含自己的区间都会有贡献。这一类题大多都可以用ST表解决。
ST表的实现?
我们以 P3865 【模板】ST 表 为例,讲述一下ST表是如何实现 $O(1)$ 地求出静态区间最大值的。
原题样例:
1
9 3 1 7 5 6 0 8
推导方程
我们令 $st[i][j]$ 表示原序列中第 $i$ 个数字起(含)往后 $2^j$ 个,也就是原数组 $a[i]$ 到 $a[i+2^j-1]$ (两边都含)的区间最大值。显然,对于单个的 $a[i]$ 的区间的最大值就是 $a[i]$ 本身。而这一段区间的长度为 $1=2^0$ 。所以我们可以得到 $st[i][0]=a[i]$ 。
然后我们继续初始化st表。我们要先定下来区间长度 $2^j$ ,再枚举第 $i$ 个数(为什么要这样的顺序呢?请往下看)。现在我们想要得出 $st[i][j]$ ,也就是 $a[i]$ 到 $a[i+2^j-1]$ 的区间最大值,应该由哪些 $st$ 转移过来呢?答案是 $st[i][j-1]$ 和 $st[i+(1«(j-1))][j-1]$ 。为什么呢?
对于一个区间,如果它的长度为 $2=2^1$ ,那么它就由两个长度为 $1$ 的区间得来(因为区间为 $1$ 的 $st$ 早就处理好了)。长度为 $4=2^2$ ,是由两个长度为 $2$ 的区间得来的。以此类推,我们发现只要把当前区间对半分,就能推导出当前区间的值了。原因很简单,我们的st表的第二位是 $2^j$ ,这也决定了它是由一个一个的 $2$ 累积起来的结果。
我们已经知道了上一个区间的长度是 $2^{j-1}$ ,也就是 $st$ 数组的第二维是 $j-1$ 。下面我们来推导第一维是几。例如,对于 $[1, 4]$ 这个区间,两个子区间是 $[1, 2]$ 和 $[3, 4]$ 。可以知道较大的那个区间的左端点是 $3$ ,这是大区间的左端点加上区间长度的一半得到的,也就是 $i+2^{j-1}$ 。由于st表只需要知道左端点和区间长度即可,那么两个 $st$ 分别是 $st[i][j-1]$ 和 $st[i+(1«(j-1))][j-1]$ 。
注意,$1«k=1^k$ ,这应该不难理解。下面是对于每个 $st$ 转移的代码:
1
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
现在也解答了两层循环遍历顺序的问题。假使我们一定要先枚举第一维 $i$ ,对于每一个 $a[i]$ 计算它在某个区间内的贡献。然而这个区间是往后的,也就是说, $a[i]$ 以后的 $st$ 全没有处理好,也就无法递推了。
循环条件
- 第一层循环:枚举 $j$ ,范围: $2 \leq len = 2^j \leq n$ ,即 $1 \leq j \leq log_2{n}$ (由于 $st[i][0]$ ,就是长度为 $1$ 的情况已经得知了,不用再来一遍)。
- 第二层循环:枚举 $i$ ,即考虑当前 $a[i]$ 对于 $j$ 所规定的区间的贡献。由于长度为 $2^j$ ,所以 $1 \leq i$ 且 $i+[1«(j-1)] \leq n$ 。刚才不是说长度为 $2^j$ 吗?那为什么不是 $i+(1«j)$ 呢?因为st表要把 $a$ 中末尾几个数字也要考虑进去。那么我们只需满足推导方程中数组中的条件 $st[i+(1«(j-1))][j-1]$ 即可。
以上理解似乎有些问题,有待改进。
区间查询
现在已经完成了预处理,要来进行查询了。给定区间 $[l, r]$ ,要求其中的最大值。如果这个 $[l, r]$ 恰好是 $st$ 中已有的区间,那最好了,直接输出。若 $[l, r]$ 的长度恰好不是 $2^j$ 的整区间呢?那就要把这个区间再分成两块。可是,即使是这样也不能保证这两个被分出来的区间的长度是 $2^j$ 。既然我们不能恰好分,那就让这两个区间有所重叠吧。于是我们得到了查询函数:
1
2
3
int solve(int l,int r){
return max(st[l][(int)log2(r-l+1)],st[r-(1<<int(log2(r-l+1)))+1][(int)log2(r-l+1)]);
}
这里应该不难理解。下面给出完整代码。
P3865 AC Code
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
#include <bits/stdc++.h>
using namespace std;
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;
}
const int maxn=1e6+5;
int n,m;
int a[maxn];
int st[maxn][(int)log2(maxn)+1];
int l,r;
int solve(int l,int r){
return max(st[l][(int)log2(r-l+1)],st[r-(1<<int(log2(r-l+1)))+1][(int)log2(r-l+1)]);
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++){
a[i]=read();
st[i][0]=a[i];
}
for(int j=1;j<=log2(n);j++){
for(int i=1;i+(1<<(j-1))<=n;i++){
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
while(m--){
l=read(),r=read();
cout<<solve(l,r)<<"\n";
}
return 0;
}