MnZn求助，MLE了，只有9分

Code:

#include<iostream>
using namespace std;
int a[500005],n,m;
struct SegTree{
    #define mid ((l+r)>>1)
    struct Node{
        int lm,rm,sm,s;
    }nod[500005<<2];
    inline int ls(int x){return x<<1;}
    inline int rs(int x){return x<<1|1;}
    void update(int x){
        nod[x].lm=max(nod[ls(x)].lm,nod[ls(x)].s+nod[rs(x)].lm);
        nod[x].rm=max(nod[rs(x)].rm,nod[rs(x)].s+nod[ls(x)].rm);
        nod[x].sm=max(max(nod[rs(x)].sm,nod[ls(x)].sm),nod[rs(x)].lm+nod[ls(x)].rm);
        nod[x].s=nod[ls(x)].s+nod[rs(x)].s;
    }
    void modi(int x,int k){
        nod[x].lm=nod[x].rm=nod[x].sm=nod[x].s=k;
    }
    void build(int x,int l,int r){
        if(l==r)modi(x,a[l]);
        else{
            build(ls(x),l,mid);
            build(rs(x),mid+1,r);
            update(x);
        }
    }
    void modify(int x,int l,int r,int pos,int k){
        if(l==r)modi(x,k);
        else{
            if(pos<=mid)modify(ls(x),l,mid,pos,k);
            else modify(rs(x),mid+1,r,pos,k);
            update(x);
        }
    }
    Node query(int x,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr)return nod[x];
        if(mid<qr&&mid>=ql){
            Node ln=query(ls(x),l,mid,ql,qr);
            Node rn=query(rs(x),mid+1,r,ql,qr);
            Node re;
            re.lm=max(ln.lm,ln.s+rn.lm);
            re.rm=max(rn.rm,rn.s+ln.rm);
            re.sm=max(max(rn.sm,ln.sm),rn.lm+ln.rm);
            re.s=rn.s+ln.s;
            return re;
        }else if(qr>mid)return query(rs(x),mid+1,r,ql,qr);
        else return query(ls(x),l,mid,ql,qr);       
    }
    #undef mid
}T;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    T.build(1,1,n);
    for(int i=1;i<=m;i++){
        int opt,a,b;
        cin>>opt>>a>>b;
        if(opt==1)cout<<T.query(1,1,n,a,b).sm<<"\n";
        else T.modify(1,1,n,a,b);
    }
    return 0;
}