首页 > 代码库 > 【倍增】RMQ的ST表算法
【倍增】RMQ的ST表算法
RMQ问题:给定一个长度为N的区间,M个询问,每次询问Li到Ri这段区间元素的最大值/最小值。
RMQ的高级写法一般有两种,即为线段树和ST表。
本文主要讲解一下ST表的写法。(以区间最大值为例)
ST表:一种利用dp求解区间最值的倍增算法。
定义:f[i][j]表示i到i+2^j-1这段区间的最大值。
预处理:f[i][0]=a[i]。即i到i区间的最大值就是a[i]。
状态转移:将f[i][j]平均分成两段,一段为f[i][j-1],另一段为f[i+2^(j-1)][j-1]。
两段的长度均为2^j-1。f[i][j]的最大值即这两段的最大值中的最大值。
得到f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1])。
void RMQ(int N){ /*注意外部循环从j开始, 因为初始状态为f[i][0], 以i为外层会有一些状态遍历不到。*/ for(int j=1;j<=20;j++) for(int i=1;i<=N;i++) if(i+(1<<j)-1<=N) f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]); }
查询:需要查询的区间为[i,j],则需要找到两个覆盖这个闭区间的最小幂区间。
这两个区间可以重复,因为两个区间是否相交对区间最值没有影响。(如下图)
当然求区间和就肯定不行了。这也就是RMQ的限制性。
因为区间的长度为j-i+1,所以可以取k=log2(j-i+1)。
则RMQ(A,i,j)=max(f[i][k],f[j-2^k+1][k])。
代码:
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; int a[100001],f[100001][20]; inline int read(){ int x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘; return x*f; } void RMQ(int N){ for(int j=1;j<=20;j++) for(int i=1;i<=N;i++) if(i+(1<<j)-1<=N) f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]); } int main(){ int N=read(),M=read(); for(int i=1;i<=N;i++) a[i]=read(); for(int i=1;i<=N;i++) f[i][0]=a[i]; RMQ(N); while(M--){ int i=read(),j=read(); int k=(int)(log((double)(j-i+1))/log(2.0)); printf("%d\n",max(f[i][k],f[j-(1<<k)+1][k])); } return 0; }
【倍增】RMQ的ST表算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。