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;
}