51nod 1174 （线段树练习 ）

题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1174

题意：求区间最大数。单点更新，段求值。

用线段树

#include<stdio.h>
#include<algorithm>
using namespace std;

struct uct{
    int maxm;
    int left,right;
};
uct tree[84004];
void build(int id ,int l,int r)
{
    tree[id].left=l;tree[id].right=r;
    if(l==r)
    {
        tree[id].maxm=max(tree[id*2].maxm,tree[id*2+1].maxm);

    }
    else
    {
        int mid=(l+r)/2;
        build(id*2,l,mid);
        build(id*2+1,mid+1,r);
        tree[id].maxm=max(tree[id*2].maxm,tree[id*2+1].maxm);

    }
}
void update(int id,int pos,int val)
{
    if(tree[id].left==tree[id].right)
        tree[id].maxm=val;
    else
    {
        int mid=(tree[id].left+tree[id].right)/2;
        if(pos<=mid)
            update(id*2,pos,val);
        else
            update(id*2+1,pos,val);
        tree[id].maxm=max(tree[id*2].maxm,tree[id*2+1].maxm);
    }
}
int  query(int id ,int l,int r)
{
    if(tree[id].left==tree[id].right)
        return tree[id].maxm;
    else
    {
        int mid=(tree[id].left+tree[id].right)/2;
        if(r<=mid)
            return query(id*2,l,r);
        else if(l>mid) return query(id*2+1,l,r);
        else
            return max(query(id*2,l,mid),query(id*2+1,mid+1,r));
    }
}
int main(void)
{
    int n,a;
    scanf("%d",&n);
    build(1,1,n);
    for(int i=0 ;i<n;i++)
    {
        scanf("%d",&a);
        update(1,i+1,a);
    }
    int q,be,en;
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d%d",&be,&en);
        int ans=query(1,be+1,en+1);
        printf("%d\n",ans);
    }

    return 0;
}