#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 1;
const int maxm = maxn << 2;
int n,q,opt,x,y,a[maxn];
struct SegmentTree{
	int Max;
	int Maxl,Maxr;
	int Sum;
}tr[maxm];
int lson(int now){return now << 1;}
int rson(int now){return now << 1 | 1;} 
void pushup(SegmentTree &now,const SegmentTree &Lson,const SegmentTree &Rson){
	if(Lson.Maxr < 0 && Rson.Maxl < 0) now.Max = max(Lson.Maxr,Rson.Maxl);
	else{
		now.Max = 0;
		if(Lson.Maxr > 0) now.Max += Lson.Maxr;
		if(Rson.Maxl > 0) now.Max += Rson.Maxl;
	}
	now.Max = max(now.Max,max(Lson.Max,Rson.Max));
	now.Maxl = max(Lson.Maxl,Rson.Maxl + Lson.Sum);
	now.Maxr = max(Rson.Maxr,Lson.Maxr + Rson.Sum);
	now.Sum = Lson.Sum + Rson.Sum;
}
void build(int now,int l,int r){
	if(l == r){
		scanf("%lld",&a[now]);
		tr[now].Max = tr[now].Maxl = tr[now].Maxr = tr[now].Sum = a[now];
		return;
	}
	int mid = (l + r) >> 1;
	build(lson(now),l,mid);
	build(rson(now),mid+1,r);
	pushup(tr[now],tr[lson(now)],tr[rson(now)]);
}
void update(int now,int l,int r,int x,int k){
	if(l == r){
		tr[now].Max = tr[now].Maxl = tr[now].Maxr = tr[now].Sum = k;
		return;
	}
	int mid = (l + r) >> 1;
	if(x <= mid) update(lson(now),l,mid,x,k);
	else update(rson(now),mid+1,r,x,k);
	pushup(tr[now],tr[lson(now)],tr[rson(now)]);
}
SegmentTree query(int now,int l,int r,int L,int R){
	if(L <= l && r <= R) return tr[now];
	int mid = (l + r) >> 1;
	if(L <= mid && R > mid){
		SegmentTree tmp;
		pushup(tmp,query(lson(now),l,mid,L,R),query(rson(now),mid+1,r,L,R));
		return tmp;
	}
	else if(L <= mid) return query(lson(now),l,mid,L,R);
	else return query(rson(now),mid+1,r,L,R);
}
signed main(){
	scanf("%lld%lld",&n,&q);
	//for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	build(1,1,n);
	while(q--){
		scanf("%lld%lld%lld",&opt,&x,&y);
		if(opt == 1){
			if(x > y) swap(x,y);
			printf("%lld\n",query(1,1,n,x,y).Max);
		}
		else update(1,1,n,x,y);
	}
	return 0;
}