#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
struct node{int ans=0,sl=0,sr=0,sum=0;};
int a[N],ans[N*4],sl[N*4],sr[N*4],sum[N*4],n,m;
int ls(int x){return x<<1;}
int rs(int x){return x<<1|1;}
int ps(int x){
	sum[x]=sum[ls(x)]+sum[rs(x)];
	ans[x]=max(ans[ls(x)],ans[rs(x)]);
	ans[x]=max(ans[x],sr[ls(x)]+sl[rs(x)]);
	sl[x]=max(sum[ls(x)]+sl[rs(x)],sl[ls(x)]);
	sr[x]=max(sum[rs(x)]+sr[ls(x)],sr[rs(x)]);
}
void build(int l,int r,int x){
	if(l==r){
		ans[x]=a[l],sl[x]=a[l],sr[x]=a[l];
		sum[x]=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,ls(x));
	build(mid+1,r,rs(x));
	ps(x);
}
void f(int l,int r,int x,int w,int k){
	if(l==r){
		a[l]=k;
		ans[x]=sl[x]=sr[x]=a[l];
		sum[x]=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	if(w<=mid) f(l,mid,ls(x),w,k);
	else f(mid+1,r,rs(x),w,k);
	ps(x);
}
node hb(node x,node y){
	node c;
	c.sum=x.sum+y.sum;
	c.ans=max(x.ans,y.ans);
	c.ans=max(c.ans,x.sr+y.sl);
	c.sl=max(x.sl,y.sl+x.sum);
	c.sr=max(y.sr,y.sum+x.sr);
	return c;
}
node qs(int l,int r,int x,int ll,int rr){
	node c1,c2;
	bool f1=false,f2=false;
	if(ll<=l&&r<=rr){
		c1.ans=ans[x];
		c1.sl=sl[x];
		c1.sr=sr[x];
		c1.sum=sum[x];
		return c1;
	}
	int mid=(l+r)>>1;
	if(mid>=ll) c1=qs(l,mid,ls(x),ll,rr),f1=true;
	if(mid+1<=rr) c2=qs(mid+1,r,rs(x),ll,rr),f2=true;
	if(f1&&f2) return hb(c1,c2);
	if(f1) return c1;
	if(f2) return c2;	
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	build(1,n,1);
	int k;
	while(m--){
		int l,r;node c;
		scanf("%d%d%d",&k,&l,&r);
		if(k==1){
			if(l>r) swap(l,r);
			c=qs(1,n,1,l,r);
			cout<<c.ans<<endl;
		}
		else f(1,n,1,l,r);
	}
	return 0;
}

MLE 改为

int a[N],ans[N*4],sl[N*4],sr[N*4],sum[N*400],n,m;

AC