学步园

题目链接:    http://poj.org/problem?id=3264

题目大意:   给出初始化的区间值，m次查询

                  每次查询区间[a，b]的最大值－最小值

解题思路:   线段树    更新: 无更新    查询:区间查询

                  建立线段树的时候，每个结点存储左右子树的最大值和最小值

                  查询时直接访问区间最大值和最小值，不需要查找到最低

                  查询时间复杂度O(logN)

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 70000
#define INF 0x3f3f3f3f
#define MAX(a,b) a>b?a:b
#define MIN(a,b) a<b?a:b
#define MID(a,b) (a+b)>>1
#define L(a) a<<1
#define R(a) (a<<1)+1

typedef struct snode{
    int left,right;
    int max,min;
}Node;

Node Tree[MAXN<<1];
int num[MAXN],minx,maxx;

void Build(int t,int l,int r)    //以t为根结点建立左子树为l，右子树为r的线段树
{
    int mid;
    Tree[t].left=l,Tree[t].right=r;
    if(Tree[t].left==Tree[t].right)
    {
        Tree[t].max=Tree[t].min=num[l];
        return ;
    }
    mid=MID(Tree[t].left,Tree[t].right);
    Build(L(t),l,mid);
    Build(R(t),mid+1,r);
    Tree[t].max=MAX(Tree[L(t)].max,Tree[R(t)].max);  //更新结点的最大值=MAX(左子树，右子树)
    Tree[t].min=MIN(Tree[L(t)].min,Tree[R(t)].min);  //更新结点的最小时=MIN(左子树，右子树)
}

void Query(int t,int l,int r)    //查询结点为t，左子树为l，右子树为r的最大值和最小值
{
    int mid;
    if(Tree[t].left==l&&Tree[t].right==r)
    {
        if(maxx<Tree[t].max)
            maxx=Tree[t].max;
        if(minx>Tree[t].min)
            minx=Tree[t].min;
        return ;
    }
    mid=MID(Tree[t].left,Tree[t].right);
    if(l>mid)
    {
        Query(R(t),l,r);
    }
    else if(r<=mid)
    {
        Query(L(t),l,r);
    }
    else
    {
        Query(L(t),l,mid);
        Query(R(t),mid+1,r);
    }
}

int main()
{
    int n,m,a,b,i;
    memset(Tree,0,sizeof(Tree));
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        scanf("%d",&num[i]);
    Build(1,1,n);            //建立以1为根结点区间为[1,n]的线段树
    while(m--)
    {
        scanf("%d%d",&a,&b);
        maxx=0;minx=INF;     //初始化最大值为0,最小值为INF
        Query(1,a,b);        //查询区间[a,b]的最大值和最小值
        printf("%d\n",maxx-minx);
    }
    return 0;
}

注:原创文章，转载请注明出处