求助线段树，只能过样例，9分WA

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=500005;
int n,m,a,x,y;
struct Segment_tree{
#define ls o<<1
#define rs o<<1|1
    struct dog{int x,s,l,r;}t[N<<2];
    void init(){memset(t,-0x3f3f3f3f,sizeof(t));}
    void pushup(int o){
        t[o].x=max(max(t[ls].x,t[rs].x),t[ls].r+t[rs].l),t[o].s=t[ls].s+t[rs].s,
        t[o].l=max(t[ls].l,t[ls].s+t[rs].l),t[o].r=max(t[ls].r,t[rs].s+t[ls].r);
    }
    void modify(int x,int y,int l=1,int r=n,int o=1){
        if(l==r){t[o]={y,y,y,y};return;}
        int mid=l+r>>1;
        if(x<=mid)modify(x,y,l,mid,ls);
        else modify(x,y,mid+1,r,rs);
        pushup(o);
    }
    dog query(int ql,int qr,int l=1,int r=n,int o=1){
        if(ql<=l&&r<=qr)return t[o];
        int mid=l+r>>1;
        dog t0,t1,res;int c;
        if(ql>mid&&qr>mid)return query(ql,qr,mid+1,r,rs);
        if(ql<=mid&&qr<=mid)return query(ql,qr,l,mid,ls);
        t0=query(ql,qr,l,mid,ls);
        t1=query(ql,qr,mid+1,r,rs);
        res.s=t0.s+t1.s;
        res.l=max(t0.l,t0.s+t1.l);
        res.r=max(t1.r,t1.s+t0.r);
        res.x=max(max(t0.x,t1.x),t0.r+t1.l);
        return res;
    }
}T;
main(){
    T.init();
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%lld",&x),
        T.modify(i,x);
    for(int i=1;i<=m;++i){
        scanf("%lld%lld%lld",&a,&x,&y);
        if(a==1){
            if(x>y)swap(x,y);
            printf("%lld\n",T.query(x,y).x);
        }
        else T.modify(x,y);
    }
}