#include <bits/stdc++.h>
#define ppiipii pair<pair<int,int>,pair<int,int> >
#define f first
#define s second
using namespace std;
int n,m,k;
int sum[1000005];
int mx[1000005];
int lmx[1000005];
int rmx[1000005];
void upd(int u,int val){
	sum[u]=mx[u]=lmx[u]=rmx[u]=val;
	u/=2;
	while(u){
		sum[u]=sum[u*2]+sum[u*2+1];
		mx[u]=max(max(mx[u*2],mx[u*2+1]),rmx[u*2]+lmx[u*2+1]);
		lmx[u]=max(lmx[u*2],sum[u*2]+lmx[u*2+1]);
		rmx[u]=max(rmx[u*2+1],sum[u*2+1]+rmx[u*2]);
		u/=2;
	}
}
ppiipii find(int l,int r,int sl,int sr,int u){
	if(r<sl||l>sr)return {{0,0},{0,0}};
	if(l>=sl&&r<=sr)return {{sum[u],mx[u]},{lmx[u],rmx[u]}};
	int mid=(r-l+1)/2;
	ppiipii t1=find(l,m,sl,sr,u*2),t2=find(m+1,r,sl,sr,u*2+1);
	return {{t1.f.f+t2.f.f,max(max(t1.f.s,t2.f.s),t1.s.s+t2.s.f)},{max(t1.s.f,t1.f.f+t2.s.f),max(t2.s.s,t2.f.f+t1.s.s)}};
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=(1<<19);i<(1<<19)+n;i++){
		scanf("%d",&sum[i]);
		mx[i]=lmx[i]=rmx[i]=sum[i];
	}
	for(int i=(1<<19)-1;i>=1;i--){
		sum[i]=sum[i*2]+sum[i*2+1];
		mx[i]=max(max(mx[i*2],mx[i*2+1]),rmx[i*2]+lmx[i*2+1]);
		lmx[i]=max(lmx[i*2],sum[i*2]+lmx[i*2+1]);
		rmx[i]=max(rmx[i*2+1],sum[i*2+1]+rmx[i*2]);
	}
	for(int i=1;i<=m;i++){
		scanf("%d",&k);
		int a,b;
		scanf("%d%d",&a,&b);
		if(k&1){
			printf("%d",find(1,(1<<19),a,b,1));
		}
		else{
			upd((1<<19)-1+a,b);
		}
	}
	return 0;
}