RMQ线段树（poj3264）

题意是求出数组某一段的最大值和最小值。

mmax[i][j]表示[i, i+2^j - 1]区间中的最大值。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
using namespace std;
int d[50005];
int mmax[50005][20];
int mmin[50005][20];
int n,m;
void Max()
{
    int i,j;
    for(i=1; i<=n; i++)
        mmax[i][0]=d[i];
    for(j=1; j<=(log((double)(n+1))/log(2.0)); j++)
        for(i=1; i+(1<<j)-1<=n; i++)
            mmax[i][j]=max(mmax[i][j-1],mmax[i+(1<<(j-1))][j-1]);
}
void Min()
{
    int i,j;
    for(i=1; i<=n; i++)
        mmin[i][0]=d[i];
    for(j=1; j<=(log((double)(n+1))/log(2.0)); j++)
        for(i=1; i+(1<<j)-1<=n; i++)
            mmin[i][j]=min(mmin[i][j-1],mmin[i+(1<<(j-1))][j-1]);
}

int getmax(int a,int b)
{
    int f;
    int l=b-a+1;
    f=(int)(log((double)l)/log(2.0));
    return (max(mmax[a][f],mmax[b-(1<<f)+1][f]));
}
int getmin(int a,int b)
{
    int f;
    int l=b-a+1;
    f=(int)(log((double)l)/log(2.0));
    return (min(mmin[a][f],mmin[b-(1<<f)+1][f]));
}
void init()
{
    Max();
    Min();
}
int main ()
{
    int a ,b;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
        scanf("%d",&d[i]);
    init();
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&a,&b);
        printf("%d\n",getmax(a,b)-getmin(a,b));
    }
    return 0;
}

RMQ线段树（poj3264）,布布扣,bubuko.com

RMQ线段树（poj3264）

原文：http://blog.csdn.net/fei____fei/article/details/20236001