rt，code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct FenKuai{
	int ll[6500],sum[6500],PreMaxSum[6500],PosMaxSum[6500],MaxAns[6500],Max[6500];
	int id[500005],a[500005],lzy[6500];
	void MakeMax(int &x,int y)
	{
		x=(x>y?x:y);
	}
	void build(int n)
	{
		int kc,PreSum,PosSum,PreMax,tot=0;
		kc=sqrt(n);
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			id[i]=(i-1)/kc+1;
			sum[id[i]]+=a[i];
			if(id[i]!=id[i-1])
			{
				ll[++tot]=i;
				PreSum=0;
				PreMax=0;
				Max[id[i]]=INT_MIN;
				PreMaxSum[id[i]]=INT_MIN;
				MaxAns[id[i]]=INT_MIN;
			}
			Max[id[i]]=max(Max[id[i]],a[i]);
			PreSum+=a[i];
			MakeMax(PreMaxSum[id[i]],PreSum);
			MakeMax(MaxAns[id[i]],PreMax=max(PreMax+a[i],0ll));
		}
		ll[tot+1]=n+1;
		for(int i=n;i>=1;i--)
		{
			if(id[i]!=id[i+1]) PosSum=0;
			PosSum+=a[i];
			MakeMax(PosMaxSum[id[i]],PosSum);
		}
	}
	void update(int l,int k)
	{
		int L=id[l];
		Max[L]=INT_MIN;
		PreMaxSum[L]=0;
		MaxAns[L]=0;
		PosMaxSum[L]=0;
		a[l]=k;
		int PreSum=0,PosSum=0,PreMax=0;
		for(int i=ll[L];i<ll[L+1];i++)
		{
			sum[L]+=a[i];
			PreSum+=a[i];
			Max[L]=max(Max[L],a[i]);
			MakeMax(PreMaxSum[L],PreSum);
			PreMax=max(PreMax+a[i],0ll);
			MakeMax(MaxAns[L],PreMax);
		}
		for(int i=ll[L+1]-1;i>=ll[L];i--)
		{
			PosSum+=a[i];
			MakeMax(PosMaxSum[L],PosSum);
		}
	}
	int querySMax(int now,int l,int r)
	{
		int ans=a[l];
		for(int i=l;i<=r;i++)
		{
			now=max(now+a[i],0ll);
			MakeMax(ans,now);
		}
		return ans;
	}
	int queryMax(int l,int r)
	{
		int L=id[l],R=id[r];
		if(L==R)
		{
			int ans=INT_MIN;
			for(int i=l;i<=r;i++) ans=max(ans,a[i]);
			if(ans<0) return ans;
			else return querySMax(0,l,r);
		}
		else
		{
			int ans=a[l],now=0,MAX=INT_MIN;
			for(int i=l;i<ll[L+1];i++)
			{
				now=max(now+a[i],0ll);
				MakeMax(ans,now);
				MAX=max(MAX,a[i]);
			}
			for(int i=L+1;i<R;i++)
			{
				MakeMax(ans,now);
				MakeMax(ans,now+PreMaxSum[i]);
				MakeMax(ans,MaxAns[i]);
				now=max(now+sum[i],PosMaxSum[i]);
				MAX=max(MAX,Max[i]);
			}
			for(int i=ll[R];i<=r;i++) MAX=max(MAX,a[i]);
			if(MAX<0) return MAX;
			else return max(ans,querySMax(now,ll[R],r));
		}
	}
}fk;
signed main()
{
	int n,q=1,l,r,op;
	cin>>n>>q;
	fk.build(n);
	while(q--)
	{
		cin>>op>>l>>r;
		if(op==1)
		{
			if(l>r) swap(l,r);
			cout<<fk.queryMax(l,r)<<'\n';
		}
		else
		{
			fk.update(l,r);
		}
	}
	return 0;
}