秋条，8pts。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int n,m;
const int N=5e5+5;
int op,x,y;
int a[N];
int treel[N<<2],treer[N<<2],treemax[N<<2],tree[N<<2];
int ls(int x){return x<<1;}
int rs(int x){return x<<1|1;}
struct node
{
	int sum,l,r,max;
};
void push_up(int p)
{
	treemax[p]=treel[rs(p)]+treer[ls(p)];
	treemax[p]=max(treemax[p],max(treemax[ls(p)],treemax[rs(p)]));
	tree[p]=tree[ls(p)]+tree[rs(p)];
	treel[p]=max(treel[ls(p)],tree[ls(p)]+treel[rs(p)]);
	treer[p]=max(treer[rs(p)],tree[rs(p)]+treer[ls(p)]);
}
void build(int s,int t,int p)
{
	if(s==t)
	{
		treel[p]=treer[p]=tree[p]=treemax[p]=a[s];
		return;
	}
	int mid=s+((t-s)>>1);
	build(s,mid,ls(p));
	build(mid+1,t,rs(p));
	push_up(p);
}
void update(int x,int k,int s,int t,int p)
{
	if(s==t)
	{
		treel[p]=treer[p]=tree[p]=treemax[p]=k;
		return;
	}
	int mid=s+((t-s)>>1);
	if(x<=mid) update(x,k,s,mid,ls(p));
	else update(s,k,mid+1,t,rs(p));
	push_up(p);
}
node query(int l,int r,int s,int t,int p)
{
	if(l<=s and t<=r) return (node){tree[p],treel[p],treer[p],treemax[p]};
	int mid=s+((t-s)>>1);
	node ansl={(int)-1e9,(int)-1e9,(int)-1e9,(int)-1e9},ansr={(int)-1e9,(int)-1e9,(int)-1e9,(int)-1e9},ans;
	if(l<=mid) ansl=query(l,r,s,mid,ls(p));
	if(mid+1<=r) ansr=query(l,r,mid+1,t,rs(p));
	ans.max=max(ansl.r+ansr.l,max(ansl.max,ansr.max));
	ans.sum=ansl.sum+ansr.sum;
	ans.l=max(ansl.l,ansl.sum+ansr.l);
	ans.r=max(ansr.r,ansr.sum+ansl.r);
	return ans;
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,n,1);
	while(m--)
	{
		cin>>op>>x>>y;
		if(op==1) cout<<query(min(x,y),max(x,y),1,n,1).max<<'\n';
		else update(x,y,1,n,1);
		//for(int i=1;i<=n*4;i++) cout<<treemax[i]<<' ';
		//cout<<'\n';
	}
	return 0;
}