线段树入门——区间最值，单点更新

佚名 6年前 (2019-04-23) 随笔 791人围观抢沙发百度已收录

线段树入门区间最值，单点更新。

题目链接：https://cn.vjudge.net/problem/HDU-1754

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn=200000;
const int maxsize=(1<<19)-1;

int data[maxsize];

void update(int v,int pos,int k,int l,int r)
{
    if(pos>=l&&pos<r)
    {
        if(r-l==1)
        {
            data[k]=v;
            return;
        }
        int m=(l+r)/2,cl=2*k+1,cr=2*k+2;
        update(v,pos,cl,l,m);
        update(v,pos,cr,m,r);
        data[k]=max(data[cl],data[cr]);
    }
}

int query(int a,int b,int k,int l,int r)
{
    if(b<=l||a>=r)
        return -1;
    if(a<=l&&b>=r)
        return data[k];
    return max(query(a,b,2*k+1,l,(l+r)/2),query(a,b,2*k+2,(l+r)/2,r));
}

int main()
{
    int n,m,v,a,b;
    char c;

    while(~scanf("%d%d",&n,&m))
    {
        memset(data,0,sizeof(data));
        for(int i=0;i<n;++i)
        {
            scanf("%d",&v);
            update(v,i,0,0,n);
        }
        while(m--)
        {
            scanf(" %c%d%d",&c,&a,&b);
            if(c=='Q')
                printf("%d\n",query(a-1,b,0,0,n));
            else update(b,a-1,0,0,n);
        }
    }

    return 0;
}