如题。

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

#define int long long
#define maxn 500005
struct SegmentTree {
    int l, r;
    int lmax, rmax, sum, dat;
} t[maxn * 4];
int n, m;
int a[maxn];

void push_up(SegmentTree &up, SegmentTree &l, SegmentTree &r) {
    up.lmax = max(l.lmax, l.sum + r.lmax);
    up.rmax = max(r.rmax, r.sum + l.rmax);
    up.sum = l.sum + r.sum;
    up.dat = max(max(l.dat, r.dat), l.rmax + r.lmax);
}

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r) { t[p].dat = t[p].lmax = t[p].rmax = t[p].sum = a[l]; return; }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid), build((p << 1) | 1, mid + 1, r);
    push_up(t[p], t[p << 1], t[(p << 1) | 1]);
}

void update(int p, int x, int v) {
    if (t[p].l == t[p].r) {
        t[p].dat = t[p].lmax = t[p].rmax = t[p].dat = v;
        return;
    }
    int mid = (t[p].l + t[p].r) >> 1;
    if (x <= mid) update(p << 1, x, v);
    if (x > mid) update((p << 1) | 1, x, v);
    push_up(t[p], t[p << 1], t[(p << 1) | 1]);
}

SegmentTree ask(int p, int l, int r) {
    if (l <= t[p].l && r >= t[p].r) return t[p];
    int mid = (t[p].l + t[p].r) >> 1;
    if (r <= mid) return ask(p << 1, l, r);
    if (l > mid) return ask((p << 1) | 1, l, r);
    SegmentTree val;
    push_up(val, ask(p << 1, l, r), ask((p << 1) | 1, l, r));
    return val;
}

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (m--) {
        int k; cin >> k;
        if (k == 1) {
            int a, b; cin >> a >> b;
            if (a > b) swap(a, b);
            cout << ask(1, a, b).dat << endl;
        }
        else {
            int p, s; cin >> p >> s;
            update(1, p, s);
        }
    }
    return 0;
}