#include<bits/stdc++.h>
using namespace std;
#define int long long
int s[1450000],ll[1450000],rr[1450000],sum[1450000],ss,lp,rp,su;
void up(int x){
	s[x]=max(rr[x*2]+ll[x*2+1],max(s[x*2],s[x*2+1]));
	ll[x]=max(ll[x*2],sum[x*2]+ll[x*2+1]);
	rr[x]=max(rr[x*2+1],sum[x*2+1]+rr[x*2]);
	sum[x]=sum[x*2]+sum[x*2+1];
}
void in(int x,int l,int r,int llp,int k){
//	cout<<x<<" "<<l<<" "<<r<<" "<<ll<<endl;
	if(llp<l||llp>r){
		return;
	}
	if(l==llp&&r==llp){
		s[x]=k;
		ll[x]=k,rr[x]=k,sum[x]=k;
		return;
	}
	int mid=(l+r)/2;
	in(x*2,l,mid,llp,k);
	in(x*2+1,mid+1,r,llp,k);
	up(x);
}
void query(int x,int l,int r,int llk,int rrk){
	if(llk>r||rrk<l){
		return;
	}
	if(llk<=l&&r<=rrk){
		int ssm=ss,lpm=lp,rpm=rp,sut=su;
		if(ssm==-1e13||lpm==-1e13||rpm==-1e13||sut==-1e13){
			ss=s[x],lp=ll[x],rp=rr[x],su=sum[x];
		}
		else{
			ss=max(rpm+ll[x],max(ssm,s[x]));
			lp=max(sut+ll[x],lpm);
			rp=max(rr[x],sum[x]+rpm);
			su=sum[x]+sut;
		}
		
		return;
	}
	int mid=(l+r)/2;
	query(x*2,l,mid,llk,rrk);
	query(x*2+1,mid+1,r,llk,rrk);
}
signed main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		in(1,1,n,i,x);
	}
	while(m--){
		int a,l,r,k;
		cin>>a>>l;
		if(a==2){
			cin>>k;
			in(1,1,n,l,k);
		}
		else{
			cin>>r;
			ss=-1e13,lp=-1e13,rp=-1e13,su=0;
			query(1,1,n,l,r);
			cout<<ss<<endl;
		}
	}
	return 0;
}