RMQ问题,全名(Range Minimum/Maximum Query),是求给定区间中的最值问题。
主要方法及复杂度如下:
1、朴素(即搜索),O(n)-O(qn) online。
2、线段树,O(n)-O(qlogn) online。
3、Sparse_Table(实质是动态规划),O(nlogn)-O(1) online。
4、RMQ标准算法:先规约成LCA(Lowest Common Ancestor),再规约成约束RMQ,O(n)-O(1) online。
昨天刚刚学了第三种,ST算法。
ST算法可以在O(nlogn)的预处理以后实现O(1)的查询效率,从而解决查询次数很多(如大于100万)的RMQ问题。
首先,是预处理。预处理是采用dp的思想,我们用f[i][j]表示区间[i,i+2^j-1]中的最大值(即从i开始,长度为2^j的闭区间)。
开始时,f[i][0]一定等于num[i]。好了,初始值找到了,下面是状态转移方程:
f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1])。即把[i,i+2^j-1]区间分成两部分[i,i+2^(j-1)-1]和[i+2^(j-1),i+2^(j-1)+2^(j-1)-1],正好和原区间一致。
有了初始值和转移方程,我们可以自底向上递推出所有的f[i][j]的值。
对于边界,还要注意一点。由于区间长度最大为n,所以二维边界最大为log(n)/log(2.0);
一维边界只要满足对于每个起始点,都可以有长度找到n就行了,也就是让i+2^j-1<=n就好了。
然后就是查询了。假设要查询区间[a,b]的最大值,由于区间的长度很可能不是2的整数幂,所以我们要把区间划分为长度为2的整数幂的两部分,而且这两个区间的并集必须是[a,b]。为了实现这个方案,我们需要先求出一个最大的k,使得2^k<=(b-a+1),这样就可以把区间分成两部分[a,a+2^k-1]和[b-2^k+1,b],使他们既能不超过a,b区间的范围,又能把区间全部覆盖。于是,[a,b]区间的最大值就等于上述两个区间的最大值中最大的那个。(有点绕)
弱弱地把代码贴上,供大家批评指正。
#include <math.h>
#include <stdio.h>
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
const int N=100005;
int n,Q,c[N],a,b;
int dp_max[N][20]; //20不一定是唯一的。需要计算log(N)/log(2)
int dp_min[N][20];
void Init()
{
for(int i=1;i<=n;i++)
dp_max[i][0] = dp_min[i][0] = c[i];
double limit = log(n)/log(2.0);
for(int j=1;j<=(int)limit;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
{
dp_max[i][j] = max(dp_max[i][j-1],dp_max[i+(1<<(j-1))][j-1]);
dp_min[i][j] = min(dp_min[i][j-1],dp_min[i+(1<<(j-1))][j-1]);
}
}
int Get_Max(int a,int b)
{
int k = (int)(log(b-a+1)/log(2.0));
return max(dp_max[a][k],dp_max[b-(1<<k)+1][k]);
}
int Get_Min(int a,int b)
{
int k = (int)(log(b-a+1)/log(2.0));
return min(dp_min[a][k],dp_min[b-(1<<k)+1][k]);
}
int main()
{
scanf("%d%d",&n,&Q);
for(int i=1;i<=n;i++)
scanf("%d",&c[i]);
Init();
while(Q--)
{
scanf("%d%d",&a,&b);
printf("%d\n",Get_Max(a,b)-Get_Min(a,b));
}
return 0;
}
分享到:
相关推荐
RMQ的sparse table算法的实现,对ACM竞赛队员非常有研究价值:)
可以实现马拉车算法 RMQ算法 tarjan算法
RMQ问题是指:对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j<=n),返回数列A中下标在[i,j]里的最小值下标。
RMQ算法,静态查找区间的最值!高效,快速!
经典RMQ问题,用来实现区间最大值和最小值的统计,预处理时间nlogn,查询时间O(1)
O(n)实现RMQ的算法,一般RMQ问题 到 O(n)构造笛卡尔树 到 <O(n), O(1)>的求解±1 RMQ问题
用st table实现区间最值RMQ的查询
这是关于ACM 相关的 RMQ问题 算法资料。
rmq算法,有详细注释 dp1[i][j] = max ( dp1[i][j-1] , dp1[i+(1(j-1))][j-1] ) ; dp2[i][j] = min ( dp2[i][j-1] , dp2[i+(1(j-1))][j-1] ) ;
RMQ 动画 这是用于创建文档中说明的动画的应用程序。 这个 repo 是一个简单的应用程序,用于说明 RMQ 可用的动画: rmq(my_view).animations.fade_in rmq(my_view).animations.fade_out rmq(my_view).animations....
ST(Sparse Table)即稀疏表,运用了动态规划的思想,设d p [ i ] [ j ] dp[i][j]dp[i][j]表示第i ii处开始的2 j 2^j2 j 个数字的最值,i ii是开始位置,j jj是延伸长度,d p [ i ] [ 0 ] dp[i][0]dp[i][0]则是原...
树状数组的总结 -rmq算法. 用树状数组实现离线rmq
2015_ble_to_rmq ble_to_rmq sample说明: 将此程式编译过的jar档放到respberry pi上执行,可以搜寻附近的BLE Device并与之连接,将透过dongle送到respberry pi的ble讯息印出来。
Ruby 动作模板用途:Promotion Promotion-menu RMQ Font Awesome
1、 概述LCA(Least Common Ancestors),即最近公共祖先,是指这样一个问题:在有根树中,找出某两个结点u和v最近的公共祖先(另一种说法
该ppt讲了一种基于线段树的RMQ的ST算法问题和LCA算法,适合初学者用。
算法合集之RMQ与LCA问题PPT学习教案.pptx
算法文档无代码RMQ&LCA问题提取方式是百度网盘分享地址
最小公祖问题的算法。 如“重新审阅LCA问题”中所述,这将使用“范围最小查询”实现LCA。 已完成:天真RMQ,更快RMQ(使用nlogn稀疏表) 待办事项:执行±1 RMQ 天真的RMQ输出: (1(2(4..)(5..))(3(6..)(7..)))...
Structure rsq(range sum query) help to find sum on segment l and r O(log(l-r+1)) and update O(logN)