#2 - #11 WA

求调……

#include<bits/stdc++.h>
#define int long long
using namespace std;

struct node{
	int l, r, sum, val, lv, rv;
}tree[500005 * 4];

int a[500005];

void pushup(int id){
	tree[id].sum = tree[id * 2].sum + tree[id * 2 + 1].sum; 
	tree[id].val = max(tree[id * 2].val, max(tree[id * 2 + 1].val, tree[id * 2].rv + tree[id * 2 + 1].lv));
	tree[id].lv = max(tree[id * 2].lv, tree[id * 2 + 1].lv + tree[id * 2].sum);
	tree[id].rv = max(tree[id * 2].rv, tree[id * 2 + 1].rv + tree[id * 2].sum);
}

void build(int id, int l, int r){
	tree[id].l = l;
	tree[id].r = r;
	if(l == r){
		tree[id].sum = a[l];
		tree[id].val = a[l];
		tree[id].lv = a[l];
		tree[id].rv = a[l];
	}
	else{
		int mid = (l + r) / 2;
		build(id * 2, l, mid);
		build(id * 2 + 1, mid + 1, r);
		pushup(id);
	}
}

node query(int id, int l, int r){
	if(tree[id].l >= l && tree[id].r <= r){
		return tree[id];
	}
	node a, b, ans;
	a.lv = a.rv = a.val = -1e9;
	b.lv = b.rv = b.val = -1e9;
	ans.val = -1e9;
	int mid = (tree[id].l + tree[id].r) / 2;
	a.sum = b.sum = ans.sum = 0;
	if(l <= mid){
		a = query(id * 2, l, r);
		ans.sum += a.sum;
	}
	if(r > mid){
		b = query(id * 2 + 1, l, r);
		ans.sum += b.sum;
	}
	ans.val = max(a.val, max(b.val, a.rv + b.lv));
	ans.lv = max(a.lv, b.lv + a.sum);
	ans.rv = max(a.rv, a.rv + b.sum);
	if(l > mid){
		ans.lv = max(ans.lv, b.lv);
	}
	if(r < mid){
		ans.rv = max(ans.rv, a.rv);
	}
	return ans;
}

void update(int id, int x, int v){
	if(tree[id].l == x && tree[id].r == x){
		tree[id].sum = tree[id].lv = tree[id].rv = tree[id].val = v;
	}
	else{
		int mid = (tree[id].l + tree[id].r) / 2;
		if(x <= mid) update(id * 2, x, v);
		else update(id * 2 + 1, x, v);
		pushup(id);
	}
}

signed main()
{
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	build(1, 1, n);
	while(m--){
		int op;
		cin >> op;
		if(op == 1){
			int l, r;
			cin >> l >> r;
			if(l > r){
				swap(l, r);
			}
			node a = query(1, l, r);
			cout << a.val << endl;
		}
		else{
			int x, k;
			cin >> x >> k;
			update(1, x, k);
		}
	}
	return 0;
}