rmq范围最小（大）指问题——处理对于n个数，要求快速求出某区间内的最值。
f[i][j]表示以i为起点长度为2^j的最值。
f[i][j] = rmq(f[i][j-1], f[i + 2 ^ (j-1)][j-1];相当于把线段分成相等的左右两段合并求rmq。但这得让线段长度是2的幂次。
查询时，例如f[1，7] = f[1][2] + f[5][1] + f[7][0];为O(logn),f[1, 7]对应于数组中的区间
为了加快查询，可使f[1，7] = f[1][2] + f[4][2];为O(1)，这里用2=（2^k <= 7）k的最大值7 - 2^2 + 1 为4，即让7向左移动2^2 - 1个位，2^k = 1 << k;注意：例如给出n=7，则f[4][2]是求对应于[4, 8]的rmq，而f[4, 8] = f[4, 7],所以要对此进行预处理,让右区间的值超过n的为右区间为n时的值，这样才能加快查询，即多增加了一些方便查询的数据。最大左移是k = log2(n),可表示的最大起始点是1 << k,则f[i][j]表示的右区间的最大值为
(1 << k) + (1 << k) = 1 << (k + 1) = 2 ^ (log2(n) + 1),提供这个数据时能给出何时得空间[n + 1][log2(n) + 1 + 1]。
代码：

#include  < stdio.h >
#include  < stdlib.h >
#include  < math.h >
#define  maxn 50010
#define  Min(a, b) a < b ? a : b
#define  Max(a, b) a > b ? a : b
struct  t
{
     int  min, max;
}map[maxn][ 20 ];
 void  build ( int  n)
{
     int  i, j, m, r  =  n, c  =  log(( double )n)  /  log( 2.0 );
     for  (i  =   1 ; i  <=  c; i ++ )
    {
         for  (j  =   1 ; j  <=  r; j ++ )
        {
            m  =  j  +  ( 1   <<  (i  -   1 )); // 右半部分的起始值
             if  (m  <=  r)
            {
                map[j][i].min  =  Min(map[j][i - 1 ].min ,map[m][i - 1 ].min);
                map[j][i].max  =  Max(map[j][i - 1 ].max, map[m][i - 1 ].max);
            }
             else // 长度超出n的，就当是j起点的最后一个终点的rmq。实现这步能使查询为O(1).
            {
                map[j][i].min  =  map[j][i - 1 ].min;
                map[j][i].max  =  map[j][i - 1 ].max;
            }
        }
    }
}
 int  query( int  l,  int  r)
{
     int  len  =  r  -  l  +   1 ;
     int  k  =  log(( double )len)  /  log( 2.0 );
     int  m  =  r  -  ( 1   <<  k)  +   1 ;
     int  min  =  Min(map[l][k].min, map[m][k].min);
     int  max  =  Max(map[l][k].max, map[m][k].max);
     return  max  -  min;
}
 int  main()
{
     int  n, m,  i, l, r;
    scanf( " %d%d " ,  & n,  & m);
     for  (i  =   1 ; i  <=  n; i ++ )
    {
        scanf( " %d " ,  & map[i][ 0 ].min);
        map[i][ 0 ].max  =  map[i][ 0 ].min;
    }
    build (n);
     while  (m -- )
    {
        scanf( " %d%d " ,  & l,  & r);
        printf( " %d\n " , query(l, r));
    }
     return   0 ;
}