ST表（Sparse Table）

一、介绍

1.作用——可重复贡献问题

对于操作$opt$，满足$?l\le k\le r,opt[l,r]=opt(opt[l,k],opt[k,r])$，例如$RMQ$区间求最值，又如区间$GCD$，都可以称为可重复贡献问题。
而ST表就是用于解决以$RMQ$问题为代表的可重复贡献问题。

2.ST表的优劣

之前我们学习过线段树，同样可以用于解决$RMQ$问题，与线段树相比，稀疏表的码量更少，但同样，稀疏表所适合的情况也更局限一些。
稀疏表包含两个过程，分别是预处理和查询，预处理的时间复杂度为$O(nlogn)$,而查询可以在$O(1)$内实现。
稀疏表的局限在于不支持在线修改，一旦预处理结束后，就只能对静态的区间进行查询（一般情况）。

二、实现（基于RMQ）

我们以$st[i][j]$表示 m a x { a [ k ] ∣ i ≤ k ≤ i + 2 j ? 1 } max\{a[k]\mid i\leq k \leq i+2^j-1\} max{ a[k]∣i≤k≤i+2j?1}

1.预处理

思路与动态规划一致，自左向右，自上往下递推出结果。
需要注意一下计算顺序！！！

递推式：$st[i][j]=max(st[i][j?1],st[i+(1<<(j?1))][j?1])$
基于$?l\le k\le r,opt[l,r]=opt(opt[l,k],opt[k,r])$

for(int j=1;j<=logn;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]);}}

2.查询

若给定任意区间范围$[l,r]$，如何根据$st[i][j]$求出对应结果？
a n s = m a x { s t [ l ] [ k ] , s t [ r ? ( 1 < < k ) + 1 ] [ k ] } ans=max\{st[l][k],st[r-(1<<k)+1][k]\} ans=max{ st[l][k],st[r?(1<<k)+1][k]}

$st[l][k]$表示区间$[l,l+2^k?1]$
$st[r?(1<<k)+1][k]$表示区间$[r?2^k+1,r]$
为了保证区间的重叠，应满足$r?2^k+1\le l+2^k?1$
化为:$\frac{r?l}{2}+1\le 2^k$
对式子两边取对数，
得：$lo{g}_2(\frac{r?l}{2}+1)\le k$

若$k$直接取$lo{g}_2(\frac{r?l}{2}+1)$,可以得到一个唯一的中间点$\frac{r+l}{2}$，看上去这应该是理想的值，但实际上我们很难使得$k$恰好等于$lo{g}_2(\frac{r?l}{2}+1)$，首先是计算$\frac{r?l}{2}$要考虑结果会自动舍去小数部分，其次是计算对数也需要化为整型，依然会舍去小数部分，这些都会使得最终计算出来的$k$小于$lo{g}_2(\frac{r?l}{2}+1)$。

所以我们令$k$等于$lo{g}_2(r?l+1)$,不必考虑除法计算，虽然计算过程中仍然要考虑对数化为整型的情况，但可以保证两个子区间可以覆盖大的区间。

3.对数优化

过程中需要多次使用log，本来可以直接使用$STL$中的函数，但为了避免超时，可以直接倍增打表。
$$log[i]=\{\begin{array}{ll}?1& i=0\\ log[\frac{i}{2}]+1& i>0\end{array}$$

4.模板代码

模板题

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int logn=log2(N);
int n,m;
int st[N][logn];
int Logn[N]; 
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(){
    n=read();m=read();Logn[0]=-1;for(int i=1;i<=n;i++){
    st[i][0]=read();Logn[i]=Logn[i/2]+1;//计算以2为底的对数 }for(int j=1;j<=Logn[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]);}}int l,r,k;while(m--){
    l=read();r=read();k=Logn[r-l+1];printf("%d\n",max(st[l][k],st[r-(1<<k)+1][k]));}
}

三、例题

最大数

题目链接
可以使用线段树，但也采用稀疏表的变形——逆稀疏表，每次更新只需对最后一行进行更新即可。
以$st[i][j]$表示 m a x { a [ k ] ∣ i ? 2 j + 1 ≤ k ≤ i } max\{a[k]\mid i-2^j+1\leq k \leq i\} max{ a[k]∣i?2j+1≤k≤i}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5; 
const int logn=log2(N);
ll st[N][logn];
ll Logn[N];
ll cnt;
ll m,d,n;
char c;
void pre(){
    Logn[0]=-1;for(int i=1;i<N;i++){
    Logn[i]=Logn[i/2]+1;//计算以2为底的对数}
}ll query(ll L){
    int l=cnt-L;int r=cnt-1;int k=Logn[r-l+1];return max(st[r][k], st[l+(1<<k)-1][k]);
}void insert(ll val){
    st[cnt][0]=val;for (int i=1;cnt-(1<<i)+1>=0;i++){
    st[cnt][i]=max(st[cnt][i-1],st[cnt-(1<<(i-1))][i-1]);}cnt++;
}int main(){
    pre();cin>>m>>d;ll t=0;while (m--){
    cin>>c>>n;if (c=='A'){
    n=(n+t)%d;insert(n);}else if (c=='Q'){
    cout<<(t=query(n))<<endl;}}return 0;
}