今天在NYOJ上看到一个编号为119的题目（由于本人初学线段树，所以急切地找有关线段树的题目）

题目大意是告诉你一个数字序列的每一个数字，对于每一条询问x，y，写出从第x个数到第y个数的最大值与最小值的差。

首先一看，我一心认为这是一个线段是的题目，于是我用链表写了一个线段树，交上去以后才发现悲剧了，TML，难道线段树还不够强大吗？

后来我看了最有解答后才发现，对于处理区间最值，尤其是当询问的次数较多的时候，有一个和线段树的强度差不多，甚至更强的算法——RMQ算法。

算法的大意是把整个区间看成是由1，2,，4，8，16等长度组成的区间，这样记录最值，然后由前面i-1可以递推出i，继而迅速得出最大值与最小值。

具体代码如下：

＃i nclude <iostream>
＃i nclude <stdio.h>
＃i nclude <cmath>
using namespace std;
int fmaxm[20][101010],fminm[20][101010],n,m,i,j,l,k,now,maxm,minm;
int main()
{
    scanf("%d %d",&n,&m);
    for ( i=1; i<=n; i++) { scanf("%d",&fmaxm[0][i]); fminm[0][i]=fmaxm[0][i]; }
    for ( i=1; i<20; i++)
    {
        for (j=1; j+(1<<i)<=n; j++)
          {
              fmaxm[i][j]=max(fmaxm[i-1][j],fmaxm[i-1][j+(1<<(i-1))]);
              fminm[i][j]=min(fminm[i-1][j],fminm[i-1][j+(1<<(i-1))]);
          }
    }
    int x,y;
    for (l=1; l<=m; l++)
    {
        scanf("%d %d",&x,&y);
        if (x==y) { printf("0\n"); continue;}
        k=y-x;
        k=int ( (log(k)+0.1)/log(2) ); if (y-x==8) k=3;
        now=x; maxm=fmaxm[0][y]; minm=fminm[0][y];
        while (k>=0)
        {
            while (now+(1<<k)<=y)
            {
                if (fmaxm[k][now]>maxm) maxm=fmaxm[k][now];
                if (fminm[k][now]<minm) minm=fminm[k][now];
                now+=1<<k;
            }
            k-=1;
        }
        printf("%d\n",maxm-minm);
    }
    return 0;
}

有图片为证（此题的时限是2000MS）