ST表的定义
ST表，又名稀疏表，是一种基于倍增思想，用于解决可重复贡献问题的数据结构
倍增思想
这里列举一个去寻找一个区间内的最大值的例子
因为每次会将将区间增大一倍，所以才被称之为倍增思想 ，这种思想十分好用，建议友友们平常多多练习
ST表的适用范围
如果A区间和B区间可能有重叠的部分
但是并不影响A+B区间的答案，能通过 A区间答案 和 B区间答案 就加工出来
那么对应的区间询问，就是一个可重复贡献问题
例如:区间最大值，区间最小值、区间公约数等，但是区间求和就不符合这个要求
再例如:区间按位与、区间按位或，ST表都能高效地解决
ST表的优势和劣势
RMQ问题(Range Maximum/Minimum Query)可以用ST表维护，也可以用线段树等结构维护
ST表的优势:构建过程时间复杂度0(n*logn)，单次查询时间复杂度0(1)，代码量较小
ST表的劣势:需要空间较大，能维护的信息非常有限，不支持修改操作
只能维护静态区间内的可重复贡献类问题，不能维护动态的
模版
预处理模版：
//st[i][j]表示的是以i为起点，长度为2^j的区间的最值
//外层循环遍历的是长度的指数，内层循环遍历的是起点
for(int j=1;j<20;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]);
}
} 查询模版：
//maxn是统计给定区间的最值
//k是用来判断区间的长度
//l，r是给定的区间范围
for(int i=1;i<=m;i++)
{
cin>>l>>r;
int k=log2(r-l+1);
maxn=max(dp[l][k],dp[r-(1<<k)+1][k]);
} 例题：
P3865 【模板】ST 表 && RMQ 问题
思路：十分板正的一个ST表板题，就是去求区间内的一个最大值，纯板题
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
int l, r;
int st[100005][20];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> st[i][0];
}
for (int j = 1; j < 20; 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]);
}
}
for (int i = 1; i <= m; i++) {
cin >> l >> r;
int k = log2(r - l + 1);
cout << max(st[l][k], st[r - (1 << k) + 1][k]) << "\n";
}
return 0;
}P2880 [USACO07JAN] Balanced Lineup G
思路：也是ST表的板题，只不过是去求一遍最大值的ST表，然后再去求一遍最小值的ST表，然后减去就可以了
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q;
int f_max[50005][17];
int f_min[50005][17];
int l,r;
signed main()
{
cin>>n>>q;
for(int i=1;i<=n;i++)
{
cin>>f_max[i][0];
f_min[i][0]=f_max[i][0];
}
for(int j=1;j<=16;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
{
f_max[i][j]=max(f_max[i][j-1],f_max[i+(1<<(j-1))][j-1]);
f_min[i][j]=min(f_min[i][j-1],f_min[i+(1<<(j-1))][j-1]);
}
}
for(int i=1;i<=q;i++)
{
cin>>l>>r;
int k=log2(r-l+1);
cout<<max(f_max[l][k],f_max[r-(1<<k)+1][k])-min(f_min[l][k],f_min[r-(1<<k)+1][k])<<"\n";
}
}P2251 质量检测
思路1：滑动窗口问题，可以直接单调队列解决，去寻找m区间长度的窗口内的最小值，但是和今天的主题不相符，这种写法就靠看官自己去琢磨了
思路2：ST表，这题是求区间内的最小值，但是却是给你规定了区间大小，让你找出整个区间的这么大小的最小值，直接预处理一遍，然后遍历即可，但是如果m不是2^k，就找到最大的k， 然后用m-(2^k)+1的k区间长度，去找最小值即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int st[1000005][25];
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>st[i][0];
}
for(int j=1;j<=21;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
{
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
int k=log2(m);
for(int i=1;i+m-1<=n;i++)
{
cout<<min(st[i][k],st[i+m-(1<<k)][k])<<"\n";
}
return 0;
}P1890 gcd区间
思路：区间gcd也是一种可重复贡献问题，因此也可以用ST表，我们直接预处理一遍，然后直接跑即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int st[1005][15];
int l,r;
int gcd(int a,int b)
{
if(b==0)
return a;
return gcd(b,a%b);
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>st[i][0];
}
for(int j=1;j<=14;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
{
st[i][j]=gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
for(int i=1;i<=m;i++)
{
cin>>l>>r;
int k=log2(r-l+1);
cout<<gcd(st[l][k],st[r-(1<<k)+1][k])<<"\n";
}
return 0;
}P4155 [SCOI2015] 国旗计划
思路：这题其实一开始我也没看出来是ST表的题目，后来想了好久我才恍然大悟，我们首先来看题，每个士兵都有自己负责的一个区域，为L和R，然后呢，我们有m个边防站，然后我们要遍历第i个士兵必须参与的情况下，最少需要多少个哨兵
我们首先需要拆环为链，我们之间将这个数组拷贝一遍，再延伸出来一个长度，然后我们去处理士兵负责的范围，加入右区间的端点，小于左区间端点，那么我们就直接将右区间的端点+m即可，然后我们再去复制每个哨兵一次，其区间的值都+m
然后我们就跑ST表，表示从i开始往后2^j次方能够达到什么位置，如果是当前这个人的左区间+m的位置，那么就说明覆盖了整个哨所，那就是可以了，我们需要去处理一下
然后直接写即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int l,r;
struct node{
int l;
int r;
int pos;
}a[400005];
int st[400005][25];
int sum[400004];
bool cmp(node a,node b)
{
return a.l<b.l;
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>l>>r;
if(l>r)
{
r+=m;
}
a[i].l=l;
a[i].r=r;
a[i].pos=i;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
{
a[i+n].l=a[i].l+m;
a[i+n].r=a[i].r+m;
}
for(int i=1,j=1;i<=2*n;i++)
{
while(j<=2*n&&a[j].l<=a[i].r)
{
j++;
}
st[i][0]=j-1;
}
for(int j=1;j<=20;j++)
{
for(int i=1;i+(1<<j)-1<=2*n;i++)
{
st[i][j]=st[st[i][j-1]][j-1];
}
}
for(int i=1;i<=n;i++)
{
int flag=a[i].l+m;
int ans=0;
int p=i;
for(int j=20;j>=0;j--)
{
if(st[p][j]&&a[st[p][j]].r<flag)
{
ans+=1<<j;
p=st[p][j];
}
}
sum[a[i].pos]=ans+2;
}
for(int i=1;i<=n;i++)
{
cout<<sum[i]<<" ";
}
return 0;
}Frequent values
思路：我们应当用到题目说的有序，我们可以将每一种数视为一个桶，然后将每个桶内的个数去求出来，然后去记录每个桶的左端点和右端点，然后我们在询问的时候，然后我们去预处理桶的数目的ST表，表示从第i个桶开始长度为2^j次方的桶内的最大值，然后我们再去找两边的最大值，然后去处理三部分最大值的最大值即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q;
int a;
int l[500005];
int r[500005];
int st[500005][24];
int num[500005];
int x,y;
void ini()
{
memset(l,0,sizeof(l));
memset(r,0,sizeof(r));
memset(st,0,sizeof(st));
memset(num,0,sizeof(num));
}
signed main()
{
while(cin>>n)
{
if(n==0)
{
break;
}
ini();
cin>>q;
int len=0;
int flag=-0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
cin>>a;
if(a!=flag)
{
r[len]=i-1;
len++;
l[len]=i;
flag=a;
}
st[len][0]++;
num[i]=len;
}
r[len]=n;
for(int j=1;j<=20;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]);
}
}
for(int i=1;i<=q;i++)
{
cin>>x>>y;
if(x>y)
swap(x,y);
if(num[x]==num[y])
{
cout<<y-x+1<<"\n";
}
else
{
int ans=0;
int L=num[x]+1;
int R=num[y]-1;
if(L<=R)
{
int k=0;
while((1<<(k+1))<=R-L+1) k++;
ans=max(ans,max(st[L][k],st[R-(1<<k)+1][k]));
}
ans=max(ans,max(y-l[num[y]]+1,r[num[x]]-x+1));
cout<<ans<<"\n";
}
}
}
return 0;
}
