经典的RMQ题目。RMQ问题是求给定区间中的最值问题。朴素算法是O(n)的，用线段树可以将算法优化到O（logn)（在线段树中保存线段的最值）。

不过，只查询的话RMQ算法最合适：它可以在O(nlogn)的预处理以后实现O(1)的查询效率。线段树主要的区别是可以修改区间，RMQ不行。

下面把Sparse Table算法分成预处理和查询两部分来说明。 使用了倍增思想。

预处理:

以求最大值为例，设d[i,j]表示[i,i+2^j-1]这个区间内的最大值，那么在询问到[a,b]区间的最大值时答案就是max(d[a,k], d[b-2^k+1,k])，其中k是满足2^k<=b-a+1(即长度)的最大的k,即k=[ln(b-a+1)/ln(2)]。

d的求法可以用动态规划，d[i, j]=max(d[i, j-1],d[i+2^(j-1), j-1])。

所以我们可以采用自底向上的算法递推地给出所有符合条件的d(i, j)的值。

查询:

查询的巧妙之处是将[m, n]这段分成两个部分重叠的的区间

于是我们就可以把[m, n]分成两个(部分重叠的)长度为2^k的区间: [m, m+2^k-1], [n-2^k+1, n];

此题几个注意的地方：1. 要注意递推的时候按长度从2^0到2^j递推，j的循环要放在外面；2. log函数用的时候，里面参数是double；3. 求2的power是常用操作，使用左移<<操作非常合适；4. cin/cout会超时，要使用scanf/printf。

#include 
     
      #include 
      
       using namespace std;#define LEN 50005#define LOG_LEN 20#define MAX(a,b) (a>b?a:b)#define MIN(a,b) (a