线段树9分，求调，玄关，不返回结构体的做法（可能不及时

#include<bits/stdc++.h>
#define NN 500050
typedef long long ll;
using namespace std;
ll m,n;
struct P{
    ll l,r,s,sl,sr,sum;
};
P tr[4*NN];
ll inp[NN];
vector<ll>ans;
void f(ll k){
    tr[k].s=max(tr[2*k].s,tr[2*k+1].s);// 
    tr[k].sl=tr[2*k].sl;
    tr[k].sr=tr[2*k+1].sr;
    tr[k].sum=tr[2*k].sum+tr[2*k+1].sum;
    if(tr[2*k].sr+tr[2*k+1].sl>=tr[k].s){
        tr[k].s=tr[2*k].sr+tr[2*k+1].sl;// 
    }
    tr[k].sl=max(tr[k].sl,tr[2*k].sum+tr[2*k+1].sl);
    tr[k].sr=max(tr[k].sr,tr[2*k+1].sum+tr[2*k].sr);
    tr[k].s=max(tr[k].s,tr[k].sl);//
    tr[k].s=max(tr[k].s,tr[k].sr);//
}
void build(ll k,ll l,ll r){
    tr[k].l=l;
    tr[k].r=r;
    if(l==r){
        tr[k].s=inp[l];
        tr[k].sl=inp[l];
        tr[k].sr=inp[l];
        tr[k].sum=inp[l];
    }else{
        build(2*k,l,(l+r)/2);
        build(2*k+1,(l+r)/2+1,r);
        f(k);
    }
}
void change(ll k,ll x,ll y){
    ll L=tr[k].l;
    ll R=tr[k].r;
    if(L==R && L==x){
        tr[k].s=y;
        tr[k].sum=y;
        tr[k].sl=y;
        tr[k].sr=y;
    }else{
        ll mid=(L+R)/2;
        if(mid>=x){
            change(2*k,x,y);
        }else{
            change(2*k+1,x,y);
        }
        f(k);
    }
}

ll ask(ll k,ll l,ll r,ll isl){
    ll L=tr[k].l;
    ll R=tr[k].r;
    if(isl){//右往左逼近 
        if(R<=r){//直到满足条件 
            return tr[k].sl;
        }else{
            return ask(2*k,l,r,isl);
        }
    }else{
        if(l<=L){
            return tr[k].sr;
        }else{
            return ask(2*k+1,l,r,isl);
        }
    }
}

ll find(ll k,ll l,ll r){
    ll L=tr[k].l;
    ll R=tr[k].r;
    if(l<=L && R<=r){
        return tr[k].s;
    }
    ll mid=(L+R)/2;
    ll a=-1e18;
    ll b=-1e18;
    ll c=-1e17;
    ll d=-1e17;
    if(mid>=l){
        a=find(2*k,l,r);//左区间最值
        d=ask(2*k,l,r,0);
    }
    if(mid+1<=r){
        b=find(2*k+1,l,r);//右区间最值
        c=ask(2*k+1,l,r,1);
    }
    //c+d是中间链接部分最值
    return max(a,max(b,c+d));
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>inp[i];
    }
    build(1,1,n);
    while(m--){
        ll a,b,c;
        cin>>c>>a>>b;
        if(c==1){
            if(a>b){
                ll t=a;
                a=b;
                b=t;
            }
            ans.push_back(find(1,a,b));
        }else{
            change(1,a,b);
        }/*
        for(int i=1;i<=2*n;i++){
            cout<<tr[i].l<<" "<<tr[i].r<<" "<<tr[i].sum<<" "<<tr[i].s<<" "<<tr[i].sl<<" "<<tr[i].sr<<endl;
        }
        cout<<endl;*/
    }
    for(auto p=ans.begin();p!=ans.end();p++){
        cout<<*p<<endl;
    }
    return 0;
}