浅谈st表

浅谈st表"/>

浅谈st表

st表的概念

st表可以用于处理静态（不修改）的rmq问题（区间最值问题）O(logn)预处理 ，O(1)查询。是一种操作简单的数据结构。

st表的实现

st表通过倍增，区间dp来实现。

st表预处理：

void init()
{for(int i=1;i<=lg[n];i++){for(int j=1;j+(1<<i)-1<=n;j++){st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);st[j][i]=gcd(g[j][i-1],g[j+(1<<(i-1))][i-1]);}}
}

st表查询：

int l,r;
scanf("%d %d",&l,&r);
int len=lg[r-l+1];
int x=max(h[l][len],h[r-(1<<len)+1][len]);
int y=min(s[l][len],s[r-(1<<len)+1][len]);
int gcd=gcd(st[l][len],st[r-(1<<len)+1][len]);

例题：codeforces 359D - Pair of Numbers

题意：

找到最长的区间【L，R】，并且满足区间中存在一个能将所有数整除的数，输出所有满足的答案的起始点。

题解：

我们发现区间长度存在单调性，故对区间长度进行二分。
在check函数中对该长度的每一个起点进行枚举。发现区间的最大公约数等于区间的最小值时，该区间成立。我们就只需要对该区间的最小值和最大公约数用st表维护。O(1)查询即可。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N =3e5+5;
int a[N],g[N][20],st[N][20],lg[N]={-1},n,ans;
vector<int>res;
int gcd(int a,int b)
{return b?gcd(b,a%b):a;
}
void init()
{for(int i=1;i<=lg[n];i++){for(int j=1;j+(1<<i)-1<=n;j++){st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);g[j][i]=gcd(g[j][i-1],g[j+(1<<(i-1))][i-1]);}}
}
bool check(int x)
{vector<int>vec;int len=lg[x+1];for(int i=1;i+x<=n;i++){int minn=min(st[i][len],st[i+x-(1<<len)+1][len]);int tmp=gcd(g[i][len],g[i+x-(1<<len)+1][len]);//cout<<i<<" "<<len<<" "<<minn<<" "<<tmp<<endl;if(tmp==minn)vec.push_back(i);}if(vec.size()){if(x>=ans) res=vec;return 1;}return 0;
}
void solve()
{scanf("%lld",&n);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);lg[i]=lg[i/2]+1;g[i][0]=st[i][0]=a[i];res.push_back(i);}init();int l=0,r=n-1;while(l<r){int mid=(l+r+1)>>1;if(check(mid)){ans=max(ans,mid);l=mid;}else r=mid-1;}printf("%d %d\n",res.size(),ans);for(auto i:res) printf("%d ",i);
}
int main()
{int t=1;//scanf("%d",&t);while(t--){solve();}return 0;
}