范围最值查询

维基百科,自由的百科全书
跳转至: 导航搜索

范围最值查询(Range Minimum Query),是针对数据集的一种条件查询。若给定一个数组 A[1,n],范围最值查询指定一个范围条件 i 到 j,要求取出 A[i,j]中最大/小的元素。

若A=[3,5,2,5,4,3,1,6,3],条件为 [3,8] 的范围最值查询返回 1,它是子数组 A[3,8] = [2,5,4,3,1,6]中最小的元素。

通常情况下,数组A是静态的,即元素不会变化,例如插入删除修改等,而所有的查询是以离线的方式给出的,即预先并不知道所有查询的参数。在上述条件下,将数组以特定方式进行预处理即可以使范围最值查询在常数时间内得到处理。

现有算法可以通过以线性时间O(n)对数组进行预处理以获得之后常数时间的范围最值查询处理[1],其空间复杂度O(n)。范围最值查询问题(RMQ)与最低公共祖先(LCA)问题有直接联系,它们可以互相转化。RMQ的算法常常应用在严格或者近似子串匹配等问题的处理中。

RMQ问题的常见解决方法有线段树、ST(倍增)、排序和朴素。

朴素算法就是每次查询都For一遍,时间复杂度O(NM)。 排序法就是新开一个数组记录数的位置,排序后每次查询从头到尾For一遍,找到第一个在区间中的数退出即可。编程复杂度低,但是实际效果可能并不好。最坏情况时间复杂度O(NlogN+NM),但平均情况会比朴素快那么一点。 倍增法请参见下面部分。 线段树是最快的算法,但是编程复杂度非常高,因此除非数据很大极少使用。


ST算法[编辑]

建立一个二维数组F[1..N,0..Log2 N的整数值].

在这个数组中F[I,J]表示范围I..I+2^J-1中的最大值.(例如2..5中的最大值被计为F[2,2])

建立数组的过程可以在NLogN时间内完成.具体算法类似于动态规划.

当我们需要计算一个区间中的最大值(例如3..8时),我们先求出这个区间的长度(即8-3+1=6)

然后我们算出不大于它的最大2^k值的指数(即2).我们要查询分别以3开头,和以8结尾的两个长度为2^2的区间的最大值.

显然F[3,2]和F[5,2]也就是(3..6和5..8)的最大值就是3..8的最大值.查询的时间是常数.

整个程序的时间复杂度是O(NLogN+M),M为查询数.

參考資料[编辑]

  1. ^ Fischer, Johannes; Heun, Volker (2007), "A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array.", Proceedings of the International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, Lecture Notes in Computer Science, 4614, Springer-Verlag, pp. 459–470, doi:10.1007/978-3-540-74450-4_41