重学ST表

ST表能做什么？

1. 预处理并 $O(1)$ 求出区间最大/最小值（也就是 RMQ, Range Maximum/Minimum Query ）。
2. 区间 GCD 问题。
3. 区间按位和/或。

而以上这些，都有一个特性：一个值对于好几段包含自己的区间都会有贡献。这一类题大多都可以用ST表解决。

ST表的实现？

我们以 P3865 【模板】ST 表 为例，讲述一下ST表是如何实现 $O(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$ 转移的代码：

st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);

现在也解答了两层循环遍历顺序的问题。假使我们一定要先枚举第一维 $i$ ，对于每一个 $a[i]$ 计算它在某个区间内的贡献。然而这个区间是往后的，也就是说， $a[i]$ 以后的 $st$ 全没有处理好，也就无法递推了。

循环条件

1. 第一层循环：枚举 $j$ ，范围： $2 \leq len = 2^j \leq n$ ，即 $1 \leq j \leq log_2{n}$ （由于 $st[i][0]$ ，就是长度为 $1$ 的情况已经得知了，不用再来一遍）。
2. 第二层循环：枚举 $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$ 。既然我们不能恰好分，那就让这两个区间有所重叠吧。于是我们得到了查询函数：

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

#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;
}