本文共 1679 字,大约阅读时间需要 5 分钟。
RMQ(Range Minimum/Maximum Query),即区间最值查询,即:对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j<=n),返回数列A中下标在i,j之间的最小/大值。如:数列 2,4,5,6,8,7,9,10,1,3共10个数,求下标0到下标7的最大(最小)值,那最容易想到的是遍历这个数列,找出值,其时间复杂度为O(n)。但当数据量非常大且查询很频繁时,该算法无法在有效的时间内查询出正解。因此,可以用一种比较高效的在线算法(ST算法)来解决这个问题。所谓在线算法,是指用户每输入一个查询便马上处理一个查询。该算法一般用较长的时间做预处理,待信息充足以后便可以用较少的时间回答每个查询。ST(Sparse Table)算法是一个非常有名的在线处理RMQ问题的算法,它可以在O(nlogn)时间内进行预处理,然后在O(1)时间内回答每个查询。下面,我将详细说下自己对该算法的理解。(一)首先是预处理,用动态规划(DP)解决。
设A[i]是要求区间最值的数列,F[i, j]表示从第i个数起连续2^j个数中的最大值。(DP的状态)
如数列 2,4,5,6,8,7,9,10,1,3
F[0,1]表示从下标0开始,2个元素的最大值,则F[0,1]=max(2,4)=4,F[1,2]=max(4,5,6,8)=8,而F[0,0]=max(2)=2,F[1,0]=4。因此F[i,0]就等于A[i]。(DP的初始值)
这样,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=2,j=2时就是5,6和 8,7这两段。F[i,j]就是这两段各自最大值中的最大值。于是我们得到了状态转移方程F[i, j]=max(F[i,j-1], F[i + 2^(j-1),j-1])。预处理代码:
举个例:如果我们要查询(2,7)这个区间的最大值(即:从下标2开始,到下标7这其间的数据哪个最大),则取 K=log2(j-i+1)=log2(7-2+1)=2 { j-i+1是区间的长度},即区间元素个数。k将这个区间分成了两个长度为2^k的块。查最大值就是找这两个区间的最大值,即:RMQ(i,j)=max(F[i,k],F[j-2^k+1,k]);此例
RMQ(2,7)=max(F[2,2],F[4,2])=max(8,10)=10。F[2,2]对应的DP[2][2],F[4,2]对应的DP[4][2]。所以预处理后,查询某区间的值时间复杂度为O(1)
总结:这就是RMQ