【朝夕的ACM笔记】目录与索引
ST表
前言
ST(Sparse Table)表，中文名稀疏表，是一种数据结构。
ST表常用于解决可重复贡献问题。
什么是可重复贡献问题？
举例来说：要你求10个数中的大数，你完全可以先求前6个数的 ，再求后7个数的
，然后再对所求的两个大数求
。虽然中间有几个数被重复计算了，但并不影响后的答案。
常见的可重复贡献问题有：区间值、区间按位和、区间按位或、区间GCD等。二而像区间和这样的问题就不是可重复贡献问题。
一、ST表的构建
这里以区间值作为例子来构建ST表。
ST表是基于倍增算法的。
我们设 表示区间
内的值，显然
。
由倍增思想可得，跳 步相当于先跳
步再跳
步；同理区间
内的值相当于是区间
和
内的值。
所以可得式子 。
则只需要枚举起点（也就是枚举 ），接着枚举区间长度（也就是枚举
），使得整个区间被包进去，就可以构建出ST表了。
对于询问：
当询问区间 内的值时，我们当然希望直接输出
。
由上式子可以得到 。
但问题来了，我们要求 得是个整数，但经过对数运算后出的
可能是个非整数，若是对其进行取整，向下取整可能使区间变小，向上取整又可能使区间变长，显然怎么都不太合适。
所以这里有一个办法，那就是把区间 分为两个子区间。
一部分是向下取整得到的 也就是
。
为了防止向下取整使得区间可能变小带来的影响，我们再塞一个新区间 。
由于是可重复贡献问题，虽然两区间有所重叠，但不会造成影响。
ST表预处理的时间复杂度为 ，查询的时间复杂度则为
。
二、参考代码
#include<bits/stdc++.h>
using namespace std;
int f[100005][21];
int logn[100005],n,m;
inline int read()//快速读入
{
int x=,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
void pre()//预处理log值，防止查询时影响速度
{
logn[1]=,logn[2]=1;
for(int i=3;i<=n;i++)
logn[i]=logn[i/2]+1;
}
int main()
{
n=read(),m=read();
pre();
for(int i=1;i<=n;i++)
f[i][]=read();//f[i][0]显然就是其本身
for(int j=1;j<=21;j++)//2的21次方满足两百万数据，若数据变大，这里上限也要变大
for(int i=1;i+(1<<j)-1<=n;i++)
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);//倍增的处理
while(m--)//m次询问
{
int l=read(),r=read();
int lg=logn[r-l+1];
int ans=max(f[l][lg],f[r-(1<<lg)+1][lg]);//区间重叠计算
printf("%d\n",ans);
}
return ;
}
三、使用ST表处理其他问题
其实只需要对区间值ST表略作修改即可。
比如区间按位与，则只需修改以下代码：
f[i][j]=f[i][j-1]&f[i+(1<<(j-1))][j-1];//倍增的处理
ans=f[l][lg]&f[r-(1<<lg)+1][lg];//区间重叠运算
再比如区间GCD：
f[i][j]=gcd(f[i][j-1],f[i+(1<<(j-1))][j-1]);//倍增的处理
ans=gcd(f[l][lg],f[r-(1<<lg)+1][lg]);//区间重叠运算
值得一提的是，处理区间GCD时，ST表与线段树的时间复杂度基本相近，但前者却显然要好写得多。
ST表的缺点在于其只能处理可重复贡献问题，以及其不支持区间修改罢了。
四、相关例题
4.1 ST表 洛谷 P3865
裸模板题。
4.2 平衡的阵容G 洛谷 P2880
需要同时求区间大小值，多建一个数组即可。
4.3 降雨量 洛谷 P2471
同样是区间值问题，由于不涉及区间修改，用ST表可能比线段树要更好写。
其实涉及RMQ（区间值）问题的题目，只要不对区间修改，就可以考虑使用ST表。
