RMQ算法

这篇文章讲RMQ(Range Minimum/Maximum Query)算法。 RMQ:即区间最值查询。对于一个长度为n的数列A，询问关于数列A中下标在i，j间的最小或最大值。下面将介绍解决这两个问题比较高效的算法。 RMQ算法：最容易想到的解决方案是遍历，复杂度是O(n)。但当数据量非常大且查询很频繁时，该算法无法在有效的时间内查询出正解。本篇文章将介绍一种比较高效的在线算法（ST算法）解决这个问题。所谓在线算法，是指用户每输入一个查询便马上处理一个查询。该算法一般用较长的时间做预处理，待信息充足以后便可以用较少的时间回答每个查询。ST（Sparse Table）算法是一个非常有名的在线处理RMQ问题的算法，它可以在O(nlogn)时间内进行预处理，然后在O(1)时间内回答每个查询。 ①预处理：预处理用DP的思想。 首先处理DP的状态：设F[i,j]表示[i,i+2^j-1]区间的最小值。例如，F(0,0)表示[0,0]之间的最小值，F(0,2)表示[0,3]之间的最小值，F(2,4)表示[2,17]之间的最小值。 然后处理DP的初始化:不难看出F[i,0]就等于A[i]。 最后是DP的状态转移方程：将F[i,j]平均分成两段。[i,i+2^(j-1)-1]区间为一段，[i+2^(j-1),i+2^j-1]区间为一段。例如，当i=1,j=3时，分成[1,4]和[5,8]两段。所以状态转移方程：F[i,j]=max/min(F[i,j-1],F[i+2^(j-1),j-1])。 代码如下：

注意循环的顺序，会发现j在外层，i在里层。这是由于动态转移方程的意义所限制，请读者自行探索…… ②查询 假如要查询[m,n]的最大/小值，那么先求出一个最大的k。使k满足2^k<=(n-m+1)。于是我们可以将[m,n]分成两个（部分重叠的）长度为2^k的区间:[m,m+2^k-1],[n-2^k+1,n];F[m,k]为F[m,m+2^k-1]的最大/小值，F[n-2^k+1,k]是[n-2^k+1,n]的最大/小值。状态转移方程：RMQ(i,j)=max/min(F[m,k],F[n-2^k+1,k]);