学习时间：2023/10/15
CSP-S 2023 倒计时 5 days 我竟然才会ST表
简述
ST表主要用于解决 静态RMQ问题。实际上，凡是具备 可重复贡献和结合律的问题，都可以用 ST表 来解决。
ST表 的优化方式和前缀和差分类似，采取预处理，每次可以做到 \(O(1)\) 时间复杂度的查询。因此，它适用于 有大量查询操作的问题。如果牵扯到大量修改需要使用线段树或者分块等其他算法。（这就是称 ST表 适用于 静态RMQ问题而不是动态 RMQ 问题的原因）
对于静态 RMQ 问题，ST表的时间复杂度比线段树更优，而且更加好写，不容易犯错。
因此，在解决 RMQ 问题时，我们需要根据题意来选择 ST表或者线段树。
实现原理
ST表 运用了倍增的思想，实现基于动态规划，具体地，定义 \(f_{i,j}\) 表示从 \(i\) 开始连续 \(2^j\) 个数中的最大值。
初始预处理，我们可以采用动态规划的方法， 把一个区间分成两部分，第一个部分为 \((i,j-1)\)，第二个部分为 \((1>>(j-1),j-1)\)。原理如图所示。
（图片选自Pecco的文章，这里表示感谢。）
对于查询，查询区间 \((l,r)\) 中，我们将其分为两部分，分别为：
\((l,l+2^s-1),(r-2^s+1,r)\)
我们显然期望符合条件的 \(s\) 最大，考虑最优情况，当 \(l+2^s-1=r\) 时，移项：
\[2^s=r+1-l \]即：
\[s=\log_{2}(r-l+1) \]当然 \(s\) 必须是整数，我们需要向下取整，也就是：
\[s=\lfloor\log_{2}(r-l+1)\rfloor \]这是左区间的 right，也就是 \(2\) 的整次幂部分，对于右区间，查找区间 \((r-(2^s)+1,r)\) 即可。
由于我们只是需求它们两个区间的最大值，这两个区间可以重复，也就是满足上面所提到的 可重复贡献，反之，对于求区间和问题不可以使用该方法。
小技巧：对于 \(log\) 的求解，C++ 自带的log2函数太慢了，我们可以通过递推预处理。
递推式非常显然：\(log_i=log_{i\div 2}+1\)
如图：
（图片选自Pecco的文章，这里表示感谢。）
可以证明这两个区间可以覆盖区间 \(l,r\)。
具体地，对于每次查询，输出 \(max(f_{l,s},f_{r-(1>>s)+1,s})\) 即可。
模板题 & 参考代码
给定一个长度为 \(n\) 的数组 \(a\)，共有 \(m\) 次询问，每次询问给定一个区间 \((l,r)\) ,求这个区间的最大值。
Analysis
发现本题没有修改操作，只是对数组初始值进行操作，是 静态RMQ 问题，考虑 ST表。
具体见代码：
参考代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010;
int f[N][21];
int Log2[N];
int n,m;
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()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
f[i][0] = read();
}
for(int i=1;i<=20;i++)
{
for(int j=1;j+(1<<i)-1 <= n;j++)
{
f[j][i] = max(f[j][i-1],f[j+(1<<(i-1))][i-1]);
}
}
for(int i=2;i<=n;i++)
{
Log2[i] = Log2[i/2] + 1;
}
for(int i=0;i<m;i++)
{
int l , r;
l = read();
r = read();
int s = Log2[r-l+1];
cout<<max(f[l][s],f[r-(1<<s)+1][s])<<"\n";
}
return 0;
}