[模板]st表 RMQ区间最值问题

【模板】静态区间最值_牛客题霸_牛客网

st表基于倍增的思想实现

最大值最小值思路一样 这里以最大值讲解

一个序列的子区间的个数显然有n*n个 根据倍增思想 我们首先在这个规模为n*n的状态空间中选择一些2的整数次幂的位置作为代表值

设f[i][j]表示数列中子区间[i][i+2^j-1]中的最大值 也就是包括i本身 一段长度为2^j的区间最大值 递推边界显然是f[i][0]=a[i] 也就是[i,i]区间中的最大值是本身；

在递推的时候 我们把子区间成倍增长 有公式f[i][j]=max( f[i][j-1], f[i+(1<<(j-1))][j-1] ) 也就是把一个区间的最值 分为了两个区间的最值中更大的那个

代码实现

int a[N],fmaxn[N][20],fminn[N][20]; void st(){ for(int i=1;i<=n;i++)fmaxn[i][0]=a[i],fminn[i][0]=a[i]; int t=log(n)/log(2)+1; for(int j=1;j<t;j++){ for(int i=1;i<=n-(1<<j)+1;i++){ fmaxn[i][j]=max(fmaxn[i][j-1],fmaxn[i+(1<<(j-1))][j-1]); fminn[i][j]=min(fminn[i][j-1],fminn[i+(1<<(j-1))][j-1]); } } }

最值查询部分

查询区间[l,r]的最值的时候 我们先计算一个k满足2^k<=r-l+1<2^(k+1) 也就是2的k次幂小于区间长度下 然后比较以l开头的2^k个数的区间中的最大值 和 r结尾的2^k个数字的区间的最大值 因为求的是最值 所以这两个区间可以重叠 但是必须包含所有的元素

查询代码实现：

int query(int op,int l,int r){ int k=log(r-l+1)/log(2); if(op==1)return min(fminn[l][k],fminn[r-(1<<k)+1][k]); if(op==2)return max(fmaxn[l][k],fmaxn[r-(1<<k)+1][k]); }

该题完整代码实现：

#include <bits/stdc++.h> using namespace std; int n,q; const int N=5e5+5; int a[N],fmaxn[N][20],fminn[N][20]; void st(){ for(int i=1;i<=n;i++)fmaxn[i][0]=a[i],fminn[i][0]=a[i]; int t=log(n)/log(2)+1; for(int j=1;j<t;j++){ for(int i=1;i<=n-(1<<j)+1;i++){ fmaxn[i][j]=max(fmaxn[i][j-1],fmaxn[i+(1<<(j-1))][j-1]); fminn[i][j]=min(fminn[i][j-1],fminn[i+(1<<(j-1))][j-1]); } } } int query(int op,int l,int r){ int k=log(r-l+1)/log(2); if(op==1)return min(fminn[l][k],fminn[r-(1<<k)+1][k]); if(op==2)return max(fmaxn[l][k],fmaxn[r-(1<<k)+1][k]); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>q; for(int i=1;i<=n;i++)cin>>a[i]; st(); while(q--){ int op,l,r; cin>>op>>l>>r; cout<<query(op,l,r)<<'\n'; } return 0; }