学步园

题目链接:  http://acm.hdu.edu.cn/showproblem.php?pid=1754

题目大意:  给出初始化区间的值，有m次操作

                  Q a b询问[a,b]区间中的最大值，U a b将第a个元素替换为b

解题思路:  线段树    更新:单点替换   询问:区间询问

                 每次更新的时候在区间结点存储此区间的最大值，查询的时候就不需要每次都查到最下面

                 更新时间复杂度O(logN)，询问时间复杂度O(logN)

代码:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXN 200005
#define MAX(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;
}Node;
Node Tree[MAXN<<2];
int num[MAXN],max;

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=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(左子树，右子树)
}

void Insert(int t,int l,int r,int n)   //向根结点为t，左子树为l，右子树为r的区间替换元素n
{
    int mid;
    if(Tree[t].left==l&&Tree[t].right==r)
    {
        Tree[t].max=n;
        return ;
    }
    mid=MID(Tree[t].left,Tree[t].right);
    if(l>mid)
        Insert(R(t),l,r,n);
    else if(r<=mid)
        Insert(L(t),l,r,n);
    else
    {
        Insert(L(t),l,mid,n);
        Insert(R(t),mid+1,r,n);
    }
    Tree[t].max=MAX(Tree[L(t)].max,Tree[R(t)].max);  //每次插入从下往上更新
}

void Query(int t,int l,int r)        //查询根结点为t，左子树为l，右子树为r的区间最大值
{
    int mid;
    if(Tree[t].left==l&&Tree[t].right==r)
    {
        if(max<Tree[t].max)
            max=Tree[t].max;
        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()
{
    char ch;
    int n,m,i,a,b;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=1;i<=n;i++)
            scanf("%d",&num[i]);
        memset(Tree,0,sizeof(Tree));   //初始化线段树
        Build(1,1,n);                  //1节电为根结电建立线段树
        getchar();
        for(i=0;i<m;i++)
        {
            scanf("%c",&ch);
            scanf("%d%d",&a,&b);
            if(ch=='U')
                Insert(1,a,a,b);       //第a个元素的值替换成b
            else
            {
                max=0;
                Query(1,a,b);          //询问[a,b]区间的最大值
                printf("%d\n",max);
            }
            getchar();
        }
    }
    return 0;
}

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