#define INF -1000000000 
#include<iostream>
using namespace std;
const int maxn=505000;
int n,m,a[maxn],opt,x,y;
struct node{
    long long l,r,lsum,rsum,sum,all;
}smt[1050000];
struct s{
    int lsum,rsum,sum,all;
};
inline s smax(s a,s b){
    return {max(a.lsum,a.all+b.lsum),max(b.rsum,b.all+a.rsum),max(max(a.sum,b.sum),a.rsum+b.lsum),a.all+b.all};
}
inline void fz(s c,node d){
	c.lsum=d.lsum,c.rsum=d.rsum,c.sum=d.sum,c.all=d.all;
} 
inline void fu(node c,s d){
	c.lsum=d.lsum,c.rsum=d.rsum,c.sum=d.sum,c.all=d.all;
}
#define ll smt[now].l
#define rr smt[now].r
#define mid (ll+rr>>1)
#define s1 smt[now].lsum
#define s2 smt[now].rsum
#define s3 smt[now].sum
#define s4 smt[now].all
#define lson smt[now<<1]
#define rson smt[now<<1^1]
inline void pushup(int now){
	s sa,sb;fz(sa,lson);fz(sb,rson);
	s sc=smax(sa,sb);fu(smt[now],sc);
}
void build(int now){
	if(ll==rr){
		s1=s2=s3=s4=a[ll];return;
	}
	lson.l=ll,rson.r=rr,lson.r=mid,rson.l=mid+1;
	build(now<<1);build(now<<1^1);pushup(now);
}
void change(int now,int k,int val){
	if(ll==rr){
		s1=s2=s3=s4=val;return;
	}
	if(k<=mid)change(now<<1,k,val);
	else change(now<<1^1,k,val);
	pushup(now);
}
s check(int now,long long l,long long r){
	if(l==ll&&r==rr)return {s1,s2,s3,s4};
	s c={INF,INF,INF,INF},d={INF,INF,INF,INF};
	if(l<=mid)c=check(now<<1,l,min(mid,r));
	if(r>mid)d=check(now<<1^1,max(mid+1,l),r);
	if(c.sum>-9e8&&d.sum>-9e8)return smax(c,d);
	if(l<=mid)return c;return d;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	smt[1].l=1;smt[1].r=n;build(1);
	for(int i=1;i<=m;i++){
		cin>>opt>>x>>y;
		if(opt==1){if(x<=y)cout<<check(1,x,y).sum<<"\n";else cout<<check(1,y,x).sum<<"\n";}
		else change(1,x,y);
	}
	return 0;
}

样例能过，2~10全部WA