#include <iostream>
#include <algorithm>
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)
#define mid ((l + r) >> 1)

using namespace std;

const int N = 5e5 + 1;

int n, m, a[N];
struct node{
    int ans = -N, pre = -N, suf = -N, sum = 0;
}t[N << 2];

void up(int p) {
    t[p].sum = t[ls(p)].sum + t[rs(p)].sum;
    t[p].pre = max(t[ls(p)].pre, t[ls(p)].sum + t[rs(p)].pre);
    t[p].suf = max(t[rs(p)].suf, t[rs(p)].sum + t[ls(p)].suf);
    t[p].ans = max({t[ls(p)].ans, t[rs(p)].ans, t[ls(p)].suf + t[rs(p)].pre});
}

void build(int p, int l, int r) {
    if (l == r) {
        t[p].sum = a[l];
        t[p].ans = a[l];
        t[p].pre = a[l];
        t[p].suf = a[l];
        return ;
    }
    build(ls(p), l, mid), build(rs(p), mid + 1, r);
    up(p);
}

void upd(int p, int l, int r, int i, int x) {
    if (l == r) {
        t[p].sum = x;
        t[p].pre = x;
        t[p].suf = x;
        t[p].ans = x;
        return ;
    }
    if (i <= mid) upd(ls(p), l, mid, i, x);
    else upd(rs(p), mid + 1, r, i, x);
    up(p);
}

int query(int p, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return -N;
    if (ql <= l && r <= qr) return t[p].ans;
    return max(query(ls(p), l, mid, ql, qr), query(rs(p), mid + 1, r, ql, qr));
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    for (int i = 1, k; i <= m; i++) {
        cin >> k;
        if (k == 1) {
            int a, b;
            if (a > b) swap(a, b);
            cin >> a >> b;
            cout << query(1, 1, n, a, b) << '\n';
        } else {
            int p, s;
            cin >> p >> s;
            upd(1, 1, n, p, s);
        }
    }
    return 0;
}