#include<bits/stdc++.h>
using namespace std;
#define int long long
#define bui __builtin_popcount
#define pii pair<int,int>
#define se second
#define fi first
#define mid (l+r>>1)
const int inf=1e9;
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int mod=998244353;
void prt(int x){
	if(x<0)putchar('-'),x=-x;
	if(x<10)putchar(x+'0');
	else prt(x/10),putchar(x%10+'0');
}
const int N=5e5+5;
int n,m,w[N];
struct nd{
	int pmx=-inf,smx=-inf,mx=-inf,sum=0;
}a[N*4],q;
void pushup(int l,int r,int u){
	a[u].pmx=max(a[u*2].sum+a[u*2+1].pmx,a[u*2].pmx);
	a[u].smx=max(a[u*2+1].sum+a[u*2].smx,a[u*2+1].smx);
	if(a[u*2].smx<0&&a[u*2+1].pmx<0){
		a[u].mx=max(a[u*2].smx,a[u*2+1].pmx);
	}
	else {
		a[u].mx=max(0ll,a[u*2].smx)+max(0ll,a[u*2+1].pmx);
	}
	a[u].mx=max(a[u].mx,max(a[u].pmx,a[u].smx));
	a[u].sum=a[u*2].sum+a[u*2+1].sum;
}
void build(int l,int r,int u){
	if(l==r){
		a[u].sum=a[u].mx=a[u].pmx=a[u].smx=w[l];
		return;
	}
	build(l,mid,u*2);
	build(mid+1,r,u*2+1);
	pushup(l,r,u);
}
void update(int l,int r,int u,int p,int k){
	if(l==p&&r==p){
		a[u].sum=a[u].mx=a[u].pmx=a[u].smx=k;
		return;
	}
	if(p<=mid)update(l,mid,u*2,p,k);
	else update(mid+1,r,u*2+1,p,k);
	pushup(l,r,u);
}
nd query(int l,int r,int u,int lx,int rx){
	if(lx>rx)return q;
	if(l==lx&&r==rx){
		return a[u];
	}
	nd ls=query(l,mid,u*2,lx,min(mid,rx)),rs=query(mid+1,r,u*2+1,max(lx,mid+1),rx);
	int k;
	if(ls.smx<0&&rs.pmx<0){
		k=max(ls.smx,rs.pmx);
	}
	else {
		k=max(0ll,ls.smx)+max(0ll,rs.pmx);
	}
	nd ys;
	ys.pmx=max(ls.pmx,ls.sum+rs.pmx),ys.smx=max(rs.smx,rs.sum+ls.smx),ys.sum=ls.sum+rs.sum;
	ys.mx=max(ls.mx,max(rs.mx,k));
	ys.mx=max(ys.mx,max(ys.pmx,ys.smx));
	return ys;
}
void sl(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)w[i]=read();
	build(1,n,1);
	while(m--){
		int opt;
		cin>>opt;
		if(opt==1){
			int l,r;
			cin>>l>>r;
			if(l>r)swap(l,r);
			cout<<query(1,n,1,l,r).mx<<"\n";
		}
		else {
			int p,s;
			cin>>p>>s;
			update(1,n,1,p,s);
		}
	}
}
signed main(){
	int t=1;
//	cin>>t;
	while(t--)sl();
	return 0;
}