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)时间内回答每个查询。   

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

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

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

     还有种更好的方法，原理是：为了减少分割出的区间数量，允许区间重叠，这样所有的情况下最多只要两个区间就好了，见下图：

   只要求出k就好了，k=(int)((log(j-1+1.0)/log(2.0)))。

【代码】

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

   初始化：

 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     }

     查询：

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）算法

原文：http://www.cnblogs.com/wuminye/p/3524893.html