RMQ ---- ST(Sparse Table)算法

【概述】

     RMQ(Range Minimum/Maximum Query),即区间最值查询,是指这样一个问题:对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j<=n),返回数列A中下标在i,j之间的最小/大值。

     一般解决这类区间问题可以用线段树来做,比较通用。但是线段树的代码量有点多。这里介绍另一种算法,ST(Sparse Table)算法。

      ST(Sparse Table)算法是一个非常有名的在线处理RMQ问题的算法,它可以在O(nlogn)时间内进行预处理,然后在O(1)时间内回答每个查询。   

【构建】  
      该算法是基于倍增思想设计的在线算法,之所以称之为倍增,是因为算法记录从每个元素开始的连续的长度为2k的区间中元素的最值
      类似于动态规划,F[i, j]表示从第i个数起连续2j个数中 ( 区间为[i,i+2j-1] )的最值。状态转移方程F[i, j]=max/min(F[i,j-1], F[i + 2j-1,j-1]),转移时需要注意别让超界了。
     
这个状态转移方程不难想到,一张图就能说明:
RMQ ---- ST(Sparse Table)算法【查询】

     对于一个查询区间 [i,j] ,只要找到一个或者多个2的整数倍长度的区间覆盖[i,j] ,取这些区间最值的最值就是答案了。

     如何把[i,j]覆盖完整?一种办法是把区间的长度按照二进制分成多个2的整数倍区间,显然这些区间是不重叠的,这样求多次最值就能得到答案。不过这种发放增加了算法常数,一次查询可能就要求几十次最值。

     还有种更好的方法,原理是:为了减少分割出的区间数量,允许区间重叠,这样所有的情况下最多只要两个区间就好了,见下图:
RMQ ---- ST(Sparse Table)算法
   只要求出k就好了,k=(int)((log(j-1+1.0)/log(2.0)))。

【代码】

   以下代码基于数组下表从0开始。

   初始化:

RMQ ---- ST(Sparse Table)算法
 1 //n为元数的个数
 2 //bitn为n的二进制位数,取下整(int)(log(n)/log(2))
 3 for (int i=0; i<n; ++i)
 4    f[i][0]=input[i];
 5 for (int j=1; j<bitn; ++j)
 6    for (int i=0; i<n; ++i)
 7    {
 8        if (i+(1<<(j-1))>=n) break;
 9        f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
10     }
RMQ ---- ST(Sparse Table)算法

     查询:

1 int query(int s,int e)  //查询区间[s,e]的最值
2 {
3     int k=(int)((log(e-s+1.0)/log(2.0)));
4     return max(f[s][k],f[e-(1<<k)+1][k]);
5 }

RMQ ---- ST(Sparse Table)算法

上一篇:防止文件备份到iCloud和iTunes中


下一篇:java.lang.OutOfMemoryError: PermGen space及其解决方法