线段树模板，单点修改+区间最大子段和，9pts,只AC第一个点

#include <bits/stdc++.h>
#define int long long
#define N 500005
using namespace std;
inline void in (int &x){
    int f=1;x=0;char c=getchar();
    while (c>'9'||c<'0'){if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9'){x=x*10+(c^48);c=getchar();}
    x*=f;
}
int n,q,op,x,y,a[N];
struct Segment_Tree{
    int sum,ldat,rdat,dat;
}Tree[N<<2];
inline void push_up (int u){
    Tree[u].sum=Tree[u<<1].sum+Tree[u<<1|1].sum;
    Tree[u].ldat=max (Tree[u<<1].ldat,Tree[u<<1].sum+Tree[u<<1|1].ldat);
    Tree[u].rdat=max (Tree[u<<1|1].rdat,Tree[u<<1|1].sum+Tree[u<<1].rdat);
    Tree[u].dat=max (Tree[u<<1].rdat+Tree[u<<1].ldat,max (Tree[u<<1].dat,Tree[u<<1|1].dat));
}
inline void build (int l,int r,int u){
    if (l==r){Tree[u].sum=Tree[u].ldat=Tree[u].rdat=Tree[u].dat=a[l];return ;}
    int mid=l+r>>1;
    build (l,mid,u<<1);build (mid+1,r,u<<1|1);
    push_up (u);
}
inline void update (int x,int y,int l,int r,int u){
    if (l==r){Tree[u].dat=Tree[u].ldat=Tree[u].rdat=Tree[u].sum=y;return ;}
    int mid=l+r>>1;
    if (x<=mid) update (x,y,l,mid,u<<1);
    if (x>mid) update (x,y,mid+1,r,u<<1|1);
    push_up (u);
}
inline Segment_Tree query (int L,int R,int l,int r,int u){
    if (L<=l&&R>=r) return Tree[u];
    int mid=l+r>>1;
    if (mid<L) return query (L,R,mid+1,r,u<<1|1);
    if (mid>=R) return query (L,R,l,mid,u<<1);
    Segment_Tree ll,rr,Dat;
    ll=query (L,mid,l,mid,u<<1);
    rr=query (mid+1,R,mid+1,r,u<<1|1);
    Dat.sum=ll.sum+rr.sum;
    Dat.ldat=max (ll.ldat,ll.sum+rr.ldat);
    Dat.rdat=max (rr.rdat,rr.sum+ll.rdat);
    Dat.dat=max (ll.rdat+rr.ldat,max (ll.ldat,rr.rdat));
    return Dat;
}
signed main (){
    in (n);in (q);
    for (int i=1;i<=n;++i) in (a[i]);
    build (1,n,1);
    for (int i=1;i<=q;++i){
        in (op);in (x);in (y);
        if (op==1){if (x>y) swap (x,y);printf ("%lld\n",query (x,y,1,n,1).dat);}
        else update (x,y,1,n,1);
    }
    return 0;
}