样例过了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e5+5;
#define lid (id << 1)
#define rid (id << 1 | 1)
struct node{
	int l, r;
	ll ans, sum, lmax, rmax;
};
node tr[N << 2];
int a[N];
void pushup(int id){
	tr[id].sum = tr[lid].sum + tr[rid].sum;
	tr[id].lmax = max(tr[lid].lmax, tr[lid].sum + tr[rid].lmax);
	tr[id].rmax = max(tr[rid].rmax, tr[rid].sum + tr[lid].rmax);
	tr[id].ans = max(max(tr[lid].ans, tr[rid].ans), tr[lid].rmax + tr[rid].lmax);
}
void build(int id, int l, int r){
	tr[id].l = l;
	tr[id].r = r;
	if (l == r){
		tr[id].sum = tr[id].ans = tr[id].lmax = tr[id].rmax = a[l];
		return;
	}
	int mid = (tr[id].l + tr[id].r) / 2;
	build(lid, l, mid);
	build(rid, mid + 1, r);
	pushup(id);
}	
void modify(int id, int x, int y){
	if (tr[id].l == tr[id].r){
		tr[id].sum = tr[id].ans = tr[id].lmax = tr[id].rmax = y;
		return;
	}
	int mid = (tr[id].l + tr[id].r) >> 1;
	if (mid >= x) modify(lid, x, y);
	else modify(rid, x, y);
	pushup(id);
}	
node query(int id, int l, int r){
	if (l <= tr[id].l && tr[id].r <= r){
		return tr[id];
	}
	int mid = (tr[id].l + tr[id].r) / 2;
	if (r <= mid) return query(lid, l, r);
	else if (l > mid) return query(rid, l, r);
	node a = query(lid, l, r), b = query(rid, l, r), t;
	t.sum = a.sum + b.sum;
	t.lmax = max(a.lmax, a.sum + b.lmax);
	t.rmax = max(a.rmax, b.sum + a.rmax);
	t.ans = max(max(a.ans, b.ans), a.rmax + b.lmax);
	return t;
}
int main(){ 
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	int k, a1, b;
	cin >> n >> m;
	for (int i = 1;i <= n;i++) cin >> a[i];
	build(1, 1, n);
	while (m--){
		cin >> k >> a1 >> b;
		if (k == 1){
			if (a1 > b) swap(a1, b);
			cout << query(1, a1, b).ans << '\n';
		}
		else{
			modify(1, a1, b);
		}
	}
	return 0;
}