线段树9分求调，马蜂好看，思路清晰

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
struct tree{
	int l,r,ma,sum,lma,rma;
	
	tree(){
		sum=0;
		ma=lma=rma=-999999999;
		l=-1;
	} 
}t[N<<2];

void debug(){
	for(int i=1;i<(N<<2);i++){
		if(t[i].l!=-1){
			cout<<i<<" "<<t[i].l<<" "<<t[i].r<<" lma:"<<t[i].lma<<" rma:"<<t[i].rma<<" ma:"<<t[i].ma<<" sum:"<<t[i].sum<<"\n";
		}
	}
}
int a[N],n,m,x,y,k,opt;
void pushup(int now){
	t[now].sum=t[now<<1].sum+t[now<<1|1].sum;
	t[now].lma=max(t[now<<1].lma,t[now<<1].sum+t[now<<1|1].lma);
	t[now].rma=max(t[now<<1|1].rma,t[now<<1|1].sum+t[now<<1].rma);
	t[now].ma=max(t[now<<1].rma+t[now<<1|1].lma,max(t[now<<1].ma,t[now<<1|1].ma));
	//t[now].ma=max(t[now].ma,max(t[now].lma,t[now].rma));
}
void build(int now,int l,int r){
	t[now].l=l,t[now].r=r;
	if(l==r) return t[now].sum=t[now].lma=t[now].rma=t[now].ma=a[l],void();
	int mid=(l+r)>>1;
	build(now<<1,l,mid);
	build(now<<1|1,mid+1,r);
	pushup(now);
}
tree ask(int now,int l,int r){
	tree ans;
	if(l<=t[now].l&&t[now].r<=r){
		return t[now];
	}
	int mid=(t[now].l+t[now].r)>>1;
	if(r<=mid) return ask(now<<1,l,r);
	else if(l>mid) return ask(now<<1|1,l,r);
	else{
		tree a=ask(now<<1,l,t[now<<1].r),b=ask(now<<1|1,t[now<<1|1].l,r);
		ans.l=a.l,ans.r=b.r;
		ans.sum=a.sum+b.sum;
		ans.lma=max(a.sum+b.lma,ans.ma);
		ans.rma=max(b.sum+a.rma,ans.ma);
		ans.ma=max(a.ma,max(b.ma,a.rma+b.lma));
		return ans;
	}
}
void update(int now,int pos,int k){
	if(t[now].l==t[now].r and t[now].l==pos)
		return t[now].sum=t[now].lma=t[now].rma=t[now].ma=k,void();
	int mid=(t[now].l+t[now].r)>>1;
	if(pos<=mid)update(now<<1,pos,k);
	else update(now<<1|1,pos,k);
	pushup(now);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	while(m--){
		cin>>opt>>x>>y;
		if(opt==1){
			if(x>y)swap(x,y);
			tree ans=ask(1,x,y);
			cout<<ans.ma<<endl;
		}
		else update(1,x,y);
	}
	return 0;
}