#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1000005;
const int inf=1e18;


namespace fastIO{
	template<typename T> void read(T &x){
		x=0;
		char ch=getchar();T fl=1;
		while(ch<'0'||ch>'9'){if(ch=='-')fl=-1;ch=getchar();};
		while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();};
		x=x*fl;
	}
	template<typename T> void readarray(T n,T a[]){
		for(int i=1;i<=n;i++)read(a[i]);
	}
	template<typename T> void write(T x){
		if(x<0){
			x=-x;putchar('-');
		}
		if(x/10)write(x/10);
		putchar(x%10+'0');
	}
	void readstr(string &s){
		char ch=getchar();
		while(ch!=' '||ch!='\n'){
			s+=ch;	
			ch=getchar();
		}
	}
}

using namespace fastIO;
int n,m;
int a[N];
struct tree{
	int l,r;
	int sum;
	int val,lv,rv;
	tree(){
		//sum=val=lv=rv=0;
	}
}t[N<<2];

int lson(int p){return p<<1;}
int rson(int p){return (p<<1)|1;}
int md(int l,int r){return (l+r)>>1;}
void pushup(int p){
	t[p].sum=t[lson(p)].sum+t[rson(p)].sum;
	t[p].val=max(max(t[lson(p)].val,t[rson(p)].val),t[lson(p)].rv+t[rson(p)].lv);
	t[p].lv=max(t[lson(p)].lv,t[rson(p)].lv+t[lson(p)].sum);
	t[p].rv=max(t[rson(p)].rv,t[lson(p)].rv+t[rson(p)].sum);
}

void build(int p,int l,int r){
	t[p].l=l,t[p].r=r;
	if(l==r){
		t[p].sum=a[l];
		t[p].val=t[p].lv=t[p].rv=a[l];
		return ;
	}
	int mid=md(l,r);
	build(lson(p),l,mid);
	build(rson(p),mid+1,r);
	pushup(p);
}

void update(int p,int x,int k){
	if(t[p].l==t[p].r){
		t[p].sum=k;
		t[p].lv=t[p].rv=t[p].val=k;
		return ;
	}
	int mid=md(t[p].l,t[p].r);
	if(x<=mid)update(lson(p),x,k);
	else update(rson(p),x,k);
	pushup(p);
}

tree query(int p,int l,int r){
	if(l<=t[p].l&&t[p].r<=r){
		return t[p];
	}
	int mid=md(t[p].l,t[p].r);
	if(r<=mid)return query(lson(p),l,r);
	else if(l>mid)return query(rson(p),l,r);
	else{
		tree lop;
		tree a,b;
		a=query(lson(p),l,r),b=query(rson(p),l,r);
		//[p].sum=a.sum+b.sum;
		t[p].val=max(max(a.val,b.val),a.rv+b.lv);
		t[p].lv=max(a.lv,b.lv+a.sum);
		t[p].rv=max(b.rv,a.rv+b.sum);
		return lop;
	}
}

signed main(){
	read(n),read(m);
	for(int i=1;i<=n;i++)read(a[i]);
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int op,l,r;read(op);read(l),read(r);
		if(op==1){
			if(l>r)swap(l,r);
			write(query(1,l,r).val);
			putchar('\n');
		}else{
			update(1,l,r);
			//putchar('\n');
		}
	}
	return 0;
}

呜呜呜（

样例没过，找不到锅

大佬求助