1、 概述
RMQ(Range Minimum/Maximum Query),即区间最值查询,是指这样一个问题:对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j<=n),返回数列A中下标在i,j之间的最小/大值。这两个问题是在实际应用中经常遇到的问题,本文介绍了当前解决这两种问题的比较高效的算法。
2、 RMQ算法
对于该问题,最容易想到的解决方案是遍历,复杂度是O(n)。但当数据量非常大且查询很频繁时,该算法也许会存在问题。
本节介绍了一种比较高效的在线算法(ST算法)解决这个问题。所谓在线算法,是指用户每输入一个查询便马上处理一个查询。该算法一般用较长的时间做预处理,待信息充足以后便可以用较少的时间回答每个查询。ST(Sparse Table)算法是一个非常有名的在线处理RMQ问题的算法,它可以在O(nlogn)时间内进行预处理,然后在O(1)时间内回答每个查询。
首先是预处理,用动态规划(DP)解决。设A[i]是要求区间最值的数列,F[i, j]表示从第i个数起连续2^j个数中的最大值。例如数列3 2 4 5 6 8 1 2 9 7,F[1,0]表示第1个数起,长度为2^0=1的最大值,其实就是3这个数。 F[1,2]=5,F[1,3]=8,F[2,0]=2,F[2,1]=4……从这里可以看出F[i,0]其实就等于A[i]。这样,DP的状态、初值都已经有了,剩下的就是状态转移方程。我们把F[i,j]平均分成两段(因为f[i,j]一定是偶数个数字),从i到i+2^(j-1)-1为一段,i+2^(j-1)到i+2^j-1为一段(长度都为2^(j-1))。用上例说明,当i=1,j=3时就是3,2,4,5 和 6,8,1,2这两段。F[i,j]就是这两段的最大值中的最大值。于是我们得到了动态规划方程F[i, j]=max(F[i,j-1], F[i + 2^(j-1),j-1])。
然后是查询。取k=[log2(j-i+1)],则有:RMQ(A, i, j)=max{F[i,k],F[j-2^k+1,k]}。 举例说明,要求区间[2,8]的最大值,就要把它分成[2,5]和[5,8]两个区间,因为这两个区间的最大值我们可以直接由f[2,2]和f[5,2]得到。
算法伪代码如下:
当然,该问题也可以用线段树(也叫区间树)解决,算法复杂度为:O(N)~O(logN)
例题:
代码如下:
分享到:
相关推荐
RMQ(Range Minimum/Maximum Query),即区间最大/小值查询,查询的时间复杂度为O(1)
Structure rmq(range minimum or maximum query) help to find minimum or maximum on segment l and r O(log(l-r+1)) and update O(logN)
RMQ(Range Minimum/Maximum Query)问题,是求区间最大值或最小值,即范围最值问题。暴力解法是对每个询问区间循环求解,设区间长度n nn,询问次数m mm,则复杂度是O ( n m ) O(nm)O(nm)。一般还可以使用线段树求解...
可以实现马拉车算法 RMQ算法 tarjan算法
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是英文Range Maximum(Minimum) Query的缩写,顾名思义是用来求某个区间内的最大值或最小值,通常用在要多次询问一些区间的最值的问题中。
| RMQ(RANGE MINIMUM/MAXIMUM QUERY)-ST 算法 (O(NLOGN + Q)) 19 | RMQ 离线算法 O(N*LOGN)+O(1)求解 LCA 19 | LCA 离线算法 O(E)+O(1) 20 | 带权值的并查集 20 | 快速排序 20 | 2 台机器工作调度 20 | 比较...
该ppt讲了一种基于线段树的RMQ的ST算法问题和LCA算法,适合初学者用。
不能设置权限777的同学可以设置如下 chown 3000:3000 ./rmqs/logs chown 3000:3000 ./rmqs/store chown 3000:3000 ./rmq/logs chown 3000:3000 ./rmq/store 访问浏览器 localhost:8180 注意 如果你的微服务或者...
最小公祖问题的算法。 如“重新审阅LCA问题”中所述,这将使用“范围最小查询”实现LCA。 已完成:天真RMQ,更快RMQ(使用nlogn稀疏表) 待办事项:执行±1 RMQ 天真的RMQ输出: (1(2(4..)(5..))(3(6..)(7..)))...
这是一个关于后缀数组的与RMQ、LCP有关的资料。。。
RMQ问题是指:对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j<=n),返回数列A中下标在[i,j]里的最小值下标。
最全的RMQ资料,看懂了应该RMQ没问题了
算法文档无代码RMQ&LCA问题提取方式是百度网盘分享地址
各种算法资料介绍和代码事例(包括2-Sat,A*,SPFA,BFS,DFS,DBFS,Dancing Links,BM,Dijkstra,Dinic,Floyd,Gabow,KMP,Prim,MD5,SAP,RMQ,Tarjan,ST,匈牙利算法,朱刘算法等),还有很多算法,不一一列出,列出这么多,是想...
一大堆模版 自己可以下来参考 应该有200个以上吧 自己下来看看 其中一个目录 ... LCA/RMQ 有限状态自动机理论 排序 选择/冒泡 快速排序 堆排序 归并排序(OK) 基数排序 拓扑排序 排序网络
我们会学到RMQ到底是什么东西,并且会知道这样时候的LCA怎么求解,一切尽在其中!
这是关于ACM 相关的 RMQ问题 算法资料。
算法学习
关于RMQ和LCA的关系的知识,如何用RMQ和LCA的转换