学习时间: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;
}