rt,样例全0

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct st{
	int left,right;
	int maxx,maxl,maxr;
	int val=0;
}tree[400005];
int a[100005];
inline void spread(st root,st l,st r){
	if(l.maxr<0&&r.maxl<0){
		root.maxx=max(l.maxr,r.maxl);
	}else{
		root.maxx=0;
		if(l.maxr>0){
			root.maxx+=l.maxr;
		}if(r.maxl>0){
			root.maxx+=r.maxl;
		}
	}
	root.maxx=max(root.maxx,l.maxx);
	root.maxx=max(root.maxx,r.maxx);
	root.maxl=max(l.maxl,l.val+r.maxl);
	root.maxr=max(r.maxr,r.val+l.maxr);
	root.val=l.val+r.val;
}
inline void build(int l,int r,int root){
	tree[root].left=l,tree[root].right=r;
	if(tree[root].left==tree[root].right){
		tree[root].val=tree[root].maxx=tree[root].maxl=tree[root].maxr=a[l];
		return;
	} 
	int mid=(tree[root].left+tree[root].right)/2;
	build(l,mid,2*root);
	build(mid+1,r,2*root+1);
	tree[root].val=tree[root*2].val+tree[root*2+1].val;
	spread(tree[root],tree[root*2],tree[root*2+1]);
} 
void update(int root,int n,int v){
	if(tree[root].left==tree[root].right){
		tree[root].val=tree[root].maxx=tree[root].maxl=tree[root].maxr=v;
		return;
	}
	int mid=(tree[root].left+tree[root].right)/2;
	if(n<=mid) update(root*2,n,v);
	else update(root*2+1,n,v);
	spread(tree[root],tree[root*2],tree[root*2+1]);
}
inline st query(int root,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return tree[root];
	int mid=(tree[root].left+tree[root].right)/2;
	if(ql<=mid&&mid<qr){
		st reg;
		spread(reg,query(root*2,l,mid,ql,qr),query(root*2+1,mid+1,r,ql,qr));
		return reg;
	}
	else if(ql<=mid) return query(ql,qr,root*2,l,mid);
	else return query(ql,qr,root*2+1,mid+1,r);
} 
signed main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,n,1);
	while(m--){
		int op,x,y;
	    scanf("%lld",&op);
		if(op==1){
			scanf("%lld%lld",&x,&y);
			if(x>y) swap(x,y);
			printf("%lld\n",query(1,x,y,1,1).maxx);
		}else{
			scanf("%lld%lld",&x,&y);
			update(1,x,y);
		}
	}
	return 0;
}