#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct Fenwick {
    vector<ll> a;

    void init(int n) {
        a.assign(n + 1, 0);
    }

    void modify(int x, ll t) {
        for (++x; x < a.size(); x += x & -x) {
            a[x] += t;
        }
    }

    ll sum(int x) {
        ll s = 0;
        for (++x; x > 0; x -= x & -x) {
            s += a[x];
        }
        return s;
    }

    ll rangeSum(int l, int r) {
        return sum(r - 1) - sum(l - 1);
    }
};

struct Segment {
    int l = -1, r = -1;
    ll sum = 0;

    Segment() = default;
    Segment(ll x, int i) {
        sum = x, l = i, r = i + 1;
    }
    Segment(int l, int r, ll sum) : l(l), r(r), sum(sum) {
    }

    bool operator<(const Segment &oth) const {
        return sum < oth.sum;
    }
};

Segment operator+(const Segment &l, const Segment &r) {
    return l.l == -1 ? r : r.r == -1 ? l : Segment{l.l, r.r, l.sum + r.sum};
}

struct Info {
    Segment minp{}, mins{}, maxp{}, maxs{}, sum{}, maxseg{}, minseg{};
    Info() = default;
    Info(ll x, int i) {
        auto s = Segment(x, i);
        auto neutp = Segment(i, i, 0);
        auto neuts = Segment(i + 1, i + 1, 0);
        minp = min(neutp, s);
        mins = min(neuts, s);
        maxp = max(neutp, s);
        maxs = max(neuts, s);
        maxseg = max(neutp, s);
        minseg = min(neutp, s);
        sum = s;
    }
};

Info operator+(const Info &l, const Info &r) {
    if (l.minp.l == -1) {
        return r;
    }
    if (r.minp.r == -1) {
        return l;
    }
    Info res{};
    res.sum = l.sum + r.sum;
    res.minp = min(l.minp, l.sum + r.minp);
    res.maxp = max(l.maxp, l.sum + r.maxp);
    res.mins = min(r.mins, l.mins + r.sum);
    res.maxs = max(r.maxs, l.maxs + r.sum);
    res.maxseg = max({l.maxseg, r.maxseg, l.maxs + r.maxp});
    res.minseg = min({l.minseg, r.minseg, l.mins + r.minp});
    return res;
}

vector<Info> tree;
int sz = 1;

void pull(int x) {
    tree[x] = tree[x << 1] + tree[x << 1 | 1];
}

void init(int n, const vector<ll> &a) {
    sz = 1 << __lg(n) + !!(n & (n - 1));
    tree.assign(sz << 1, {});
    for (int i = 0; i < n; ++i) {
        tree[i + sz] = Info(a[i], i);
    }
    for (int i = sz - 1; i > 0; --i) {
        pull(i);
    }
}

void tmodify(int x, const Info &v) {
    for (tree[x += sz] = v; x >>= 1; ) {
        pull(x);
    }
}

Info rangeSum(int l, int r) {
    Info lhs{}, rhs{};
    for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
        if (l & 1) lhs = lhs + tree[l++];
        if (r & 1) rhs = tree[--r] + rhs;
    }
    return lhs + rhs;
}

int findFirst(int x, int l, ll hi, ll lo, ll sum) {
    if (tree[x].minp.sum + sum > lo && tree[x].maxp.sum + sum < hi || tree[x].sum.r <= l) {
        return -1;
    }
    if (x >= sz) {
        return x - sz;
    }
    int res = findFirst(x << 1, l, hi, lo, sum);
    if (res == -1) {
        return findFirst(x << 1 | 1, l, hi, lo, sum + tree[x << 1].sum.sum);
    }
    return res;
}

int findLast(int x, int r, ll hi, ll lo, ll sum) {
    if (tree[x].sum.l == -1 || tree[x].mins.sum + sum > lo && tree[x].maxs.sum + sum < hi || tree[x].sum.l >= r) {
        return -1;
    }
    if (x >= sz) {
        return x - sz;
    }
    int res = findLast(x << 1 | 1, r, hi, lo, sum);
    if (res == -1) {
        return findLast(x << 1, r, hi, lo, sum + tree[x << 1 | 1].sum.sum);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    bool allp = *min_element(a.begin(), a.end()) >= 0;

    Fenwick fn;
    fn.init(n);
    for (int i = 0; i < n; ++i) {
        fn.modify(i, a[i]);
    }

    init(n, a);

    auto query = [&](int l, int r) -> ll {
        ll ans = abs(fn.rangeSum(l, r)); // 1 block
        if (allp) {
            return ans;
        }
        auto info = rangeSum(l, r);
        for (int p : {info.maxp.r, info.minp.r}) {
            ans = max(ans, min(abs(fn.rangeSum(l, p)), abs(fn.rangeSum(p, r))));
        }
        auto check = [&](ll mid) {
            ll sx = fn.rangeSum(0, l);
            ll sy = fn.rangeSum(r, n);
            int i1 = findFirst(1, l, mid + sx, -mid + sx, 0) + 1;
            if (i1 == 0 || i1 >= r) {
                return false;
            }
            int i2 = findLast(1, r, mid + sy, -mid + sy, 0);
            if (i2 == -1 || i2 <= i1 || i2 >= r) {
                return false;
            }
            auto f = rangeSum(i1, i2);
            if (f.minseg.sum <= -mid || f.maxseg.sum >= mid) {
                return true;
            } else {
                return false;
            }
        };
        ll lo = ans, hi = ans + 100;
        while (lo + 1 < hi) {
            ll mid = lo + hi >> 1;
            if (check(mid)) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        ans = max(ans, lo);
        return ans;
    };

    auto modify = [&](int i, int x) {
        fn.modify(i, x - a[i]);
        a[i] = x;
        tmodify(i, Info(a[i], i));
        allp &= x >= 0;
    };

    while (q--) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 1) {
            cout << query(l - 1, r) << '\n';
        } else {
            modify(l - 1, r);
        }
    }

    return 0;
}