[学习笔记]ST表

前言：某次模拟赛T1被二维ST坑了。于是决心总结下。

 

ST表：O(常数)查询静态区间最值。

思想：利用倍增预处理。然后拼凑。

一维ST表：

f[i][j]表示，[i,i+(1<<j)-1]的区间最值。

lg[i]表示，log₂i

#include<bits/stdc++.h> using namespace std; const int N=100000+10; int n,m; int a[N]; int f[N][30]; int lg[N]; int main() {scanf("%d%d",&n,&m);int t;for(int i=1;i<=n;i++) scanf("%d",&t),f[i][0]=t;for(int i=1;i<=n;i++) lg[i]=(i>>lg[i-1]+1)?lg[i-1]+1:lg[i-1];for(int j=1;(1<<j)<=n;j++)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]);}int l,r;for(int i=1;i<=m;i++){scanf("%d%d",&l,&r);int len=lg[r-l+1];printf("%d\n",max(f[l][len],f[r-(1<<len)+1][len]));}return 0; }

 

二维ST表：

类似处理二维前缀和。

先求出每行单独的，然后再把行并起来。

f[i][j][k][l]表示，行[i,i+(1<<k)-1]与列[j,j+(1<<l)-1]围成的矩形的数的最值。

lg[i]同上。

#include<bits/stdc++.h> #define ri register int #define numb (ch^'0') using namespace std; typedef long long ll; const int N=303; void rd(int &x){x=0;char ch;while(!isdigit(ch=getchar()));for(x=numb;isdigit(ch=getchar());x=(x<<1)+(x<<3)+numb); } int a[N][N]; int f[N][N][12][12]; int n,m,q; int lg[N]; inline int Max(const int &a,const int &b){return a>b?a:b; } int main(){scanf("%d%d",&n,&m);int now=1,id=0;for(ri i=1;i<=max(n,m);++i){if(i==now) lg[i]=id,now*=2,++id;else lg[i]=lg[i-1];}for(ri i=1;i<=n;++i){for(ri j=1;j<=m;++j){rd(a[i][j]);f[i][j][0][0]=a[i][j];}}for(ri l=1;l<=10;++l){for(ri i=1;i<=n;++i){for(ri j=1;j+(1<<l)-1<=m;++j){f[i][j][0][l]=Max(f[i][j][0][l-1],f[i][j+(1<<(l-1))][0][l-1]);}}}for(ri k=1;k<=10;++k){for(ri l=0;l<=10;++l)for(ri i=1;i+(1<<k)-1<=n;++i){for(ri j=1;j+(1<<l)-1<=m;++j){f[i][j][k][l]=Max(f[i][j][k-1][l],f[i+(1<<(k-1))][j][k-1][l]);}}}scanf("%d",&q);int x1,x2,y1,y2;while(q--){rd(x1);rd(y1);rd(x2);rd(y2);int l1=x2-x1+1;int l2=y2-y1+1;int g1=lg[l1],g2=lg[l2];//cout<<g1<<" "<<l1<<" "<<g2<<" "<<l2<<endl;int ans=0;ans=Max(ans,f[x1][y1][g1][g2]);//cout<<ans<<endl;ans=Max(ans,f[x1][y2-(1<<g2)+1][g1][g2]);//cout<<ans<<endl;ans=Max(ans,f[x2-(1<<g1)+1][y1][g1][g2]);//cout<<ans<<endl;ans=Max(ans,f[x2-(1<<g1)+1][y2-(1<<g2)+1][g1][g2]);printf("%d\n",ans);}return 0; }

 

 

树上ST表

O(logn)查询树上两点链之间的最值。logn因为要找LCA

处理方法类比倍增LCA。跳LCA的时候顺便求出。

 

 

 

基于倍增思想的预处理。O(常数)查询。

用于卡常数还是不错的。

转载于:https://www.cnblogs.com/Miracevin/p/9856967.html

总结

以上是生活随笔为你收集整理的[学习笔记]ST表的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。