学步园

    不多说了，还是最基础的线段树，大家可以用这些题来入门线段树，最重要的是要有自己的build，query，update模板。

update： 单点替换

query：   寻求区间最大值

# include<cstdio>
# include<iostream>
# include<algorithm>

using namespace std;

# define lson l,m,rt<<1
# define rson m+1,r,rt<<1|1

const int maxn = 222222;
int MAX[maxn<<2];

void PushUP( int rt )
{//向上更新父节点
    MAX[rt] = max( MAX[rt<<1],MAX[rt<<1|1] );
}


void build( int l,int r, int rt )
{//建树的过程
    if ( r == l )
    {
        scanf("%d",&MAX[rt]);
        return;
    }
    int m = (r+l)>>1;
    build(lson);
    build(rson);
    PushUP(rt);
}

void update( int p,int sc, int l, int r,int rt )
{//单点更换
    if ( l == r )
    {
        MAX[rt] = sc;
        return;
    }
    int m = (l+r)>>1;
    if ( p<=m )
        update( p,sc,lson );
    else
        update( p,sc,rson );
    PushUP(rt);
}

int query( int L,int R,int l,int r,int rt )
{//更新区间的最大值
    if ( L<=l&&r<=R )
    {
        return MAX[rt];
    }
    int m = ( l+r )>>1;
    int ret = 0;
    if ( L<=m )
        ret = max( ret,query(L,R,lson));
    if ( R>m )
        ret = max( ret,query(L,R,rson));
    return ret;
}


int main(void)
{
    int n,m;
    while ( ~scanf("%d%d",&n,&m) )
    {
        build(1,n,1);
        while( m-- )
        {
            char op[20];
            int a,b;
            scanf("%s%d%d",op,&a,&b);
            if ( op[0] == 'Q' )
                printf("%d\n",query(a,b,1,n,1));
                else
                update(a,b,1,n,1);
        }
    }

    return 0;
}