如题，思路参考的第一篇 UKE 的题解。

#include<iostream>
#define mid ((l+r)/2)
#define int long long 
using namespace std;
int b=-1e9;
int n,m,k,p,q;
int a[500005];
struct node{
	int sum,maxl,maxn,maxr;
}tr[2000005];
void pushup(int x){
	tr[x].sum=tr[2*x].sum+tr[2*x+1].sum;
	tr[x].maxl=max(tr[2*x].maxl,tr[2*x].sum+tr[2*x+1].maxl);
	tr[x].maxr=max(tr[2*x].maxr,tr[2*x+1].sum+tr[2*x].maxr);
	tr[x].maxn=max(tr[2*x].maxr+tr[2*x+1].maxl,max(tr[2*x].maxn,tr[2*x+1].maxn));
}
void build(int x,int l,int r){
	if(l==r){
		tr[x].sum=tr[x].maxl=tr[x].maxr=tr[x].maxn=a[l];
		return ;
	}
	build(2*x,l,mid);
	build(2*x+1,mid+1,r);
	pushup(x);
}
void update(int x,int l,int r,int k,int v){
	if(l==r&&l==k){
		tr[x].maxl=tr[x].maxr=tr[x].maxn=tr[x].sum=v;
		return ;
	}
	if(k<=mid)update(2*x,l,mid,k,v);
	if(k>mid)update(2*x+1,mid+1,r,k,v);
	pushup(x);
}
node query(int x,int l,int r,int from,int to){
	if(r<from||to<l)return node{b,b,b,b};
	if(from<=l&&r<=to)return tr[x];
	if(from<=mid&&to>mid){
		node ans,lc=query(2*x,l,mid,from,to),rc=query(2*x+1,mid+1,r,from,to);
		ans.maxl=max(lc.maxl,lc.sum+rc.maxl);
		ans.maxr=max(rc.maxr,rc.sum+lc.maxr);
		ans.maxn=max(max(lc.maxn,rc.maxn),lc.maxr+rc.maxl);
		return ans;
	}
	else if(from<=mid)return query(2*x,l,mid,from,to);
	else if(to>mid)return query(2*x+1,mid+1,r,from,to);
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	while(m--){
		cin>>k>>p>>q;
		if(p>q)swap(p,q);
		if(k==1){
			cout<<query(1,1,n,p,q).maxn<<endl;
		}
		if(k==2){
			update(1,1,n,q,p);
		}
	}
	return 0;
}