spoj 1716. Can you answer these queries III

spoj  1716. Can you answer these queries III
spoj 에서 문 제 를 풀 때 누군가가 이 문 제 를 제출 하 는 것 을 보 았 습 니 다. 이름 을 보면 데이터 구조의 문제 가 분명 하 다 는 것 을 알 수 있 습 니 다. 그리고 문 제 는 간단 합 니 다........................................................................................[ l , r ]  max(sum[ i])  - min(sum[j ])  i, j 는 [l, r] 구간 내 에 있 지만 i < j 는 욕심 이 적용 되 지 않 을 수도 있 습 니 다. 그리고 걸 렸 습 니 다...........................................................
남 의 코드 를 보고 알았어 요.   http://blog.csdn.net/gotoac/article/details/7623857

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

const int maxn=50010;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long ll;
ll lsum[maxn<<2],msum[maxn<<2],rsum[maxn<<2],sum[maxn<<2];
struct Node{
   ll lsum,msum,rsum,sum;
};
void pushup(int rt)
{
    int ls=rt<<1,rs=rt<<1|1;
    lsum[rt]=max(lsum[ls],sum[ls]+lsum[rs]);
    msum[rt]=max(max(msum[ls],msum[rs]),rsum[ls]+lsum[rs]);
    rsum[rt]=max(rsum[rs],sum[rs]+rsum[ls]);
    sum[rt]=sum[ls]+sum[rs];
}
void build(int l,int r,int rt)
{
    if(l==r){
        scanf("%lld",&sum[rt]);
        lsum[rt]=rsum[rt]=msum[rt]=sum[rt];
        return;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    pushup(rt);
}
void update(int p,ll val,int l,int r,int rt)
{
    if(l==r) {
        lsum[rt]=msum[rt]=rsum[rt]=sum[rt]=val;
        return;
    }
    int m=(l+r)>>1;
    if(p<=m) update(p,val,lson);
    else update(p,val,rson);
    pushup(rt);
}
Node query(int L,int R,int l,int r,int rt)
{
    Node ret;
    if(L<=l&&R>=r){
        ret.lsum=lsum[rt],
        ret.msum=msum[rt],
        ret.rsum=rsum[rt],
        ret.sum=sum[rt];
        return ret;
    }
    int m=(l+r)>>1;
    if(R<=m) return query(L,R,lson);
    if(L>m)  return query(L,R,rson);
    Node ret1=query(L,R,lson);
    Node ret2=query(L,R,rson);
    ret.lsum=max(ret1.lsum,ret1.sum+ret2.lsum);
    ret.msum=max(max(ret1.msum,ret2.msum),ret1.rsum+ret2.lsum);
    ret.rsum=max(ret2.rsum,ret2.sum+ret1.rsum);
    ret.sum=ret1.sum+ret2.sum;
    return ret;
}
int main()
{
    int n,m,l,r,cmd;
    while(scanf("%d",&n)==1)
    {
        build(1,n,1);
        scanf("%d",&m);
        while(m--){
            scanf("%d%d%d",&cmd,&l,&r);
            if(cmd==0) update(l,r,1,n,1);
            else printf("%d
",query(l,r,1,n,1).msum);
        }
    }
    return 0;
}