#include <bits/stdc++.h>
#define int long long
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid (l + r >> 1)

using namespace std;

const int maxn = 5e5 + 1;
const int inf = 5e10;

struct node {
    int tot;
    int pre;
    int suf;
    int mx;

    node(): tot(0), pre(-inf), suf(-inf), mx(-inf) {}
};

int n, q;
int a[maxn];
node tree[maxn << 2];

void pushup(int u) {
    tree[u].tot = tree[ls].tot + tree[rs].tot;
    tree[u].pre = max(tree[ls].pre, tree[ls].tot + tree[rs].pre);
    tree[u].suf = max(tree[rs].suf, tree[ls].suf + tree[rs].tot);
    tree[u].mx = max(max(tree[ls].mx, tree[rs].mx), tree[ls].suf + tree[rs].pre);
}

void build(int u, int l, int r) {
    if (l == r) {
        tree[u].tot = a[l];
        tree[u].pre = tree[u].suf = tree[u].mx = a[l];
        return;
    }
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(u);
}

void modify(int u, int l, int r, int p, int v) {
	if (l == r) {
		tree[u].tot = v;
        tree[u].pre = tree[u].suf = tree[u].mx = v;
        return;
	}
	if (p <= mid) modify(ls, l, mid, p, v);
	if (mid < p) modify(rs, mid + 1, r, p, v);
	pushup(u);
}

node query(int u, int l, int r, int lq, int rq) {
    if (lq <= l && r <= rq) {
        return tree[u];
    }
    node ld = node(), rd = node(), ans = node();
    if (lq <= mid) ld = query(ls, l, mid, lq, rq);
    if (rq > mid) rd = query(rs, mid + 1, r, lq, rq);
    ans.tot = ld.tot + rd.tot;
    ans.pre = max(ld.pre, ld.tot + rd.pre);
    ans.suf = max(rd.suf, ld.suf + rd.tot);
    ans.mx = max(max(ld.mx, rd.mx), ld.suf + rd.pre);
    pushup(u);
    return ans;
}

signed main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    build(1, 1, n);
    for (int i = 1, op, l, r, p, v; i <= q; i++) {
        cin >> op;
        if (op == 1) {
        	cin >> l >> r;
        	node ans = query(1, 1, n, l, r);
        	cout << ans.mx << endl;
		} else {
			cin >> p >> v;
			modify(1, 1, n, p, v);
		}
    }
    return 0;
}