求调

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int maxn=5e5+10;

int n,m;
int a[maxn];

struct segment_tree{
	struct Node{
		int l,r;
		int sum;
		int maxsum;
		int lsum,rsum;
	}tr[maxn*4];
	
	void build(int p,int l,int r){
		tr[p]={l,r,-100000,-100000,-100000,-100000};
		if(l==r){
			tr[p].sum=tr[p].lsum=tr[p].rsum=tr[p].maxsum=a[l];
			return ;
		}
		
		int mid=l+r>>1;
		build(p<<1,l,mid);
		build(p<<1|1,mid+1,r);
		tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
		tr[p].lsum=max(tr[p<<1].lsum,tr[p<<1|1].lsum+tr[p<<1].sum);
		tr[p].rsum=max(tr[p<<1|1].rsum,tr[p<<1].rsum+tr[p<<1|1].sum);
		tr[p].maxsum=max(tr[p<<1].maxsum,max(tr[p<<1|1].maxsum,tr[p<<1].rsum+tr[p<<1|1].lsum));
	}
	
	void change(int p,int x,int k){
		if(tr[p].l>x||tr[p].r<x) return ;
		if(tr[p].l==x&&tr[p].r==x){
			tr[p].sum=tr[p].lsum=tr[p].maxsum=tr[p].rsum=k;
			return ;
		}
		change(p<<1,x,k);
		change(p<<1|1,x,k);
		tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
		tr[p].lsum=max(tr[p<<1].lsum,tr[p<<1|1].lsum+tr[p<<1].sum);
		tr[p].rsum=max(tr[p<<1|1].rsum,tr[p<<1].rsum+tr[p<<1|1].sum);
		tr[p].maxsum=max(tr[p<<1].maxsum,max(tr[p<<1|1].maxsum,tr[p<<1].rsum+tr[p<<1|1].lsum));
	}
	
	int check(int p,int l,int r){
		if(tr[p].l>r||tr[p].r<l) return -100000;
		if(tr[p].l>=l&&tr[p].r<=r)  return tr[p].maxsum;
		int s=-100000;
		s=max(s,check(p<<1,l,r));
		s=max(s,check(p<<1|1,l,r));
		return s;
	}
}ST;

signed main(){
	scanf("%lld %lld",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	ST.build(1,1,n);
	
	for(int i=1;i<=m;i++){
		int op,x,y;
		scanf("%lld %lld %lld",&op,&x,&y);
		if(op&1){
			if(x>y) swap(x,y);
			printf("%lld\n",ST.check(1,x,y));
		}
		else{
			ST.change(1,x,y);
		}
	}
}