ST算法

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

ST（Sparse Table）算法是基于动态规划的，用f[i][j]表示区间起点为j长度为2^i的区间内的最小值所在下标，通俗的说，就是区间[j, j + 2^i)的区间内的最小值的下标。

从定义可知，这种表示法的区间长度一定是2的幂，所以除了单位区间(长度为1的区间)以外，任意一个区间都能够分成两份，并且同样可以用这种表示法进行表示，[j, j + 2^i)的区间可以分成[j, j+2^(i-1))和[j + 2^i)，于是可以列出状态转移方程为： f[i][j] = RMQ( f[i-1][j], f[i-1][j+2^(i-1)] )。

f数组记录的是长度为偶数的子串的最值，对于正常的查询的话，并不可能每一次都是查询偶数长的区间，所以还需要在进一步的处理一下。对于查询区间[a, b], 可以将其划分为两个长度相等的偶数的子区间[a, a+2^k],[b-2^k, b],这两个区间有可能是相交的，但是不影响对区间最值的求解。现在只要根据a、b求出k，就可以知道[a, b]区间的最值了，为：min/max{f[k][a], f[k][b-(1<<k)+1]}.

对于K，需要满足a+2^k-1 >= b-2^k，则2^(k+1) >= (b-a+1), 两边取对数（以2为底），得 k+1 >= lg(b-a+1)，则k >= lg(b-a+1) - 1，k只要需要取最小的满足条件的整数即可。

初始化：

//n为元数的个数
//bitn为n的二进制位数，取下整(int)(log(n)/log(2))
for (int i=0; i<n; ++i)
   f[i][0]=input[i];
for (int j=1; j<bitn; ++j)
   for (int i=0; i<n; ++i)
   {
       if (i+(1<<(j-1))>=n) break;
       f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    }

查询：

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