#include<cstdio>
#define int long long
int a[500010];
struct seg
{
	struct node
	{
		int sum,ml,mr;
		int val;
		int l,r;
	}t[500010*4];
	int max(int a,int b)
	{
		return a>b?a:b;
	}
	void pushup(int k)
	{
		t[k].sum=t[2*k].sum+t[2*k+1].sum;
		t[k].ml=max(t[2*k].ml,t[2*k].sum+t[2*k+1].ml);
		t[k].mr=max(t[2*k+1].mr,t[2*k+1].sum+t[2*k].mr);
		t[k].val=max(max(t[2*k].val,t[2*k+1].val),t[2*k].mr+t[2*k+1].ml);
	}
	void build(int k,int l,int r)
	{
		t[k].l=l,t[k].r=r;
		if(l==r)
		{
			t[k].val=t[k].ml=t[k].mr=t[k].sum=a[l];
			return ;
		}
		int mid=(l+r)>>1;
		build(2*k,l,mid);
		build(2*k+1,mid+1,r);
		pushup(k);
	}
	void update(int k,int x,int num)
	{
		if(t[k].l==t[k].r)
		{
			t[k].val=t[k].ml=t[k].mr=t[k].sum=num;
			return ;
		}
		int mid=(t[k].l+t[k].r)>>1;
		if(x<=mid) update(2*k,x,num);
		else update(2*k+1,x,num);
		pushup(k);
	}
	node query(int k,int l,int r)
	{
		if(t[k].l>=l&&t[k].r<=r) return t[k];
		int mid=(t[k].l+t[k].r)>>1;
		if(r<=mid) return query(2*k,l,r);
		if(l>mid) return query(2*k+1,l,r);
		node re,left=query(2*k,l,r),right=query(2*k+1,l,r);
		re.sum=left.sum+right.sum;
		re.ml=max(left.ml,left.sum+right.ml);
		re.mr=max(right.mr,right.sum+left.mr);
		re.val=max(max(left.sum,right.sum),left.mr+right.ml);
		return re;
	}
}tree;
int n,m;
void swap(int &a,int &b)
{
	int tmp=a;
	a=b;
	b=tmp;
}
signed main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	tree.build(1,1,n);
	while(m--)
	{
		int op,l,r;
		scanf("%lld%lld%lld",&op,&l,&r);
		if(op==1)
		{
			if(l>r) swap(l,r);
			printf("%lld\n",tree.query(1,l,r).val);
		}
		else tree.update(1,l,r); 
	}
	return 0;
}

A#1，其余全WA，求助