分析

• 单点修改，modify中使用pushup即可。
• 查询区间内的最大连续子段和。我们要考虑每个节点内部需要存储哪些信息？首先，必须存储区间端点和对应的最大连续子段和，如下：

struct Node {
    int l, r;  // 区间左右端点
    int tmax;  // 最大连续子段和
}

• 现在考虑我们能不能使用上述信息从子节点得到父节点的最大连续子段和呢？答案是不能的，因为我们不能求出跨两个子区间的最大连续子段和，因此还需要添加属性，需要添加该区间的最大后缀和以及最大前缀和，如下：

struct Node {
    int l, r;  // 区间左右端点
    int tmax;  // 最大连续子段和
    int lmax;  // 最大前缀和
    int rmax;  // 最大后缀和
}

则此时父节点的最大连续子段和是左右孩子的tmax以及上述情况的最大值。

• 我们现在新加入了两个属性，此时还需要考虑能否从子节点得到父节点的这两个属性呢？答案是不能的，因为如果父节点的lmax或者rmax横跨两个子节点，则无法从子节点得到父节点的这两个属性，因此还需要增加属性，增加整个区间的总和，如下：

struct Node {
    int l, r;  // 区间左右端点
    int tmax;  // 最大连续子段和
    int lmax;  // 最大前缀和
    int rmax;  // 最大后缀和
    int sum;  // 区间总和
}

此时根据这些数据，可以从子节点计算出父节点的tmax, lmax, rmax，那新加入的sum能否计算出来呢？这是可以的，因为父节点的sum等于两个子节点的sum和。

• 至此，本题分析完毕。

#include <iostream>

using namespace std;

const int N = 500010;

int n, m;  // 数列长度、指令条数
int a[N];  // 输入数组
struct Node {
    int l, r;
    // 区间总和、最大前缀和、最大后缀和、最大连续子段和
    int sum, lmax, rmax, tmax;
} tr[N * 4];

// 根据u的左右孩子构造u
void pushup(Node &u, Node &l, Node &r) {

    u.sum = l.sum + r.sum;
    u.lmax = max(l.lmax, l.sum + r.lmax);
    u.rmax = max(r.rmax, l.rmax + r.sum);
    u.tmax = max(max(l.tmax, r.tmax), l.rmax + r.lmax);
}

void pushup(int u) {
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r) {

    if (l == r) tr[u] = {l, r, a[l], a[l], a[l], a[l]};
    else {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

// 从节点tr[u]开始修改第a[x]个数为v
void modify(int u, int x, int v) {

    if (tr[u].l == tr[u].r) tr[u] = {x, x, v, v, v, v};
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

// 返回从节点tr[u]开始查询区间a[l, r]的最大连续子段和所在的节点
Node query(int u, int l, int r) {

    if (tr[u].l >= l && tr[u].r <= r) return tr[u];
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid) return query(u << 1, l, r);
        else if (l > mid) return query(u << 1 | 1, l, r);
        else {
            auto left = query(u << 1, l, r);
            auto right = query(u << 1 | 1, l, r);
            Node res;
            pushup(res, left, right);  // 根据左右孩子求解tmax
            return res;
        }
    }
}

int main() {

    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    build(1, 1, n);

    int k, x, y;
    while (m--) {
        scanf("%d%d%d", &k, &x, &y);
        if (k == 1) {
            if (x > y) swap(x, y);
            printf("%d\n", query(1, x, y).tmax);
        } else {
            modify(1, x, y);
        }
    }

    return 0;
}