POJ 3264 Balanced Lineup RMQ有关问题 ST算法 O(1)查找区间最值

原题： http://poj.org/problem?id=3264

题目大意：
给定n个数的值，求区间最大值和最小值的差。

线段树可以以nlogn的效率完成预处理，以logn的效率完成查找区间最值，这里介绍一种nlogn处理，O(1)查询的方法。就是st算法。

这里我们来看一个表。

第一排表示的是以该点为起点，连续的2^0个数的最大值。
第二排表示的是以该点为起点，连续的2^1个数的最大值。
第三排表示的是以该点为起点，连续的2^2个数的最大值。
……
第n排表示的是以该点为起点，连续的2^2个数的最大值。

因为这个我们每次的数据范围扩大2，所以能由上面一层的两个最大值取大得到区间的最大值。

假设我们现在有了这么一张表。

对于任意数区间ab，我们假设存在x满足a <= x <= b，并使得x=a-1+2^k，那么我们可以把区间分成两部分（注意，这两部分可以有交集）：
[a,a+2^k-1]和[b-2^k+1,b]。
显然通过上面的dp递推式，我们可以得到以x为起点，连续2^k个数的最大值。也就是a到a-1+2^k的最大值。
然后我们求剩下区间的最大值，我们可以找到以b-2^k+1为起点，连续2^k个数的最大值。

感觉是不是有点绕？
我们举个例子，假如a=1，b=2，显然区间要分为[1,1]和[2,2]，这里的k=0。
假如a=3，b=9，那么k=2。分为[3,6]和[6,9]。
假如a=3，b=13，那么k=3。分为[3,10]和[6,13]。
因为上面两个部分的最大值我们总是已经求出来了的，所以只需要比较一次就可以得出答案，时间复杂度是O(1)。

我们像上面例表一样先建一个dp数组供查询。
建表的核心代码如下：

for(i=1;i<=log((double)n)/log(2.0);i++)
        for(j=1;j+(1<<i)-1<=n;j++)
        {
            dpmax[i][j]=max(dpmax[i-1][j],dpmax[i-1][j+(1<<(i-1))]);
        }

log((double)n)/log(2.0);这里是对数的换底公式，意思是求log2(n)向下取整。
1<<i这里是移位操作，等价于1*2^i，因为我们需要每层的dp值包含的数更多。

而取最值的算法如下：

int getmax(int a,int b)
{
    int k=(int)(log((double)(b-a+1))/log(2.0));
    return max(dpmax[k][a],dpmax[k][b-(1<<k)+1]);
}

这里用到的是上面的把区间分为两部分，求最值。

下面是参考代码：

#include <iostream>
#include"stdio.h"
#include"math.h"
using namespace std;

const int N=50005;

int a[N];
int dpmax[40][N];
int dpmin[40][N];

void rmq(int n)
{
    int i,j;
    for(i=1;i<=n;i++)
    {
        dpmin[0][i]=a[i];
        dpmax[0][i]=a[i];
    }
    for(i=1;i<=log((double)n)/log(2.0);i++)
        for(j=1;j+(1<<i)-1<=n;j++)
        {
            dpmax[i][j]=max(dpmax[i-1][j],dpmax[i-1][j+(1<<(i-1))]);
            dpmin[i][j]=min(dpmin[i-1][j],dpmin[i-1][j+(1<<(i-1))]);
        }
}

int getmax(int a,int b)
{
    int k=(int)(log((double)(b-a+1))/log(2.0));
    return max(dpmax[k][a],dpmax[k][b-(1<<k)+1]);
}
int getmin(int a,int b)
{
    int k=(int)(log((double)(b-a+1))/log(2.0));
    return min(dpmin[k][a],dpmin[k][b-(1<<k)+1]);
}



int main()
{
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        rmq(n);
        for(int i=1;i<=m;i++)
        {
            int a,b;
            scanf("%d %d",&a,&b);
            printf("%d\n",getmax(a,b)-getmin(a,b));
        }
    }
    return 0;
}