//P4513
#include <algorithm>
#include <cstdio>
using namespace std;

const int maxn=500010;
int a[maxn];
struct SegmentTree{
	struct node{
		int sum,lm,rm,am;
	} t[maxn<<2];
	inline void update(int n){
		t[n].sum=t[n<<1].sum+t[n<<1|1].sum;
		t[n].lm=t[n<<1].lm;
		t[n].rm=t[n<<1|1].rm;
		t[n].am=max(max(t[n].lm,t[n].rm),t[n<<1].rm+t[n<<1|1].lm);
		return;
	}
	inline void buildtree(int l,int r,int n){
		if(l==r){
			t[n].sum=t[n].lm=t[n].rm=t[n].am=a[l];
			return;
		}
		int mid=l+r>>1;
		buildtree(l,mid,n<<1),buildtree(mid+1,r,n<<1|1),update(n);
		return;
	}
	inline void modify(int l,int r,int n,int k,int val){
		if(l==r){
			t[n].sum=t[n].lm=t[n].rm=t[n].am=val;
			return;
		}
		int mid=l+r>>1;
		if(k<=mid) modify(l,mid,n<<1,k,val);
		else modify(mid+1,r,n<<1|1,k,val);
		update(n);
		return;
	}
	inline node ask(int l,int r,int n,int ll,int rr){
		if(ll<=l&&r<=rr) return t[n];
		int mid=l+r>>1;
		if(rr<=mid) return ask(l,mid,n<<1,ll,rr);
		if(ll>mid) return ask(mid+1,r,n<<1|1,ll,rr);
		node x=ask(l,mid,n<<1,ll,rr),y=ask(mid+1,r,n<<1|1,ll,rr),res;
		res.sum=x.sum+y.sum;
		res.lm=max(x.lm,x.sum+y.lm);
		res.rm=max(y.rm,x.rm+y.sum);
		res.am=max(max(x.am,y.am),x.rm+y.lm);
		return res;
	}
} T;

int main(){
	int n,m,k,A,b;
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; ++i)
		scanf("%d",&a[i]);
	T.buildtree(1,n,1);
	for(int i=1; i<=m; ++i){
		scanf("%d%d%d",&k,&A,&b);
		switch(k){
			case 1:
				if(A>b) swap(A,b);
				printf("%d\n",T.ask(1,n,1,A,b).am);
				break;
			case 2:
				T.modify(1,n,1,A,b);
				break;
		}
	}
	return 0;
}

样例是过的，但只得了九分