【线段树】你能回答这些问题吗

题目

245. 你能回答这些问题吗

---

给定长度为 $N$ 的数列 $A$，以及 $M$ 条指令，每条指令可能是以下两种之一：

1. 1 x y，查询区间 $[x,y]$ 中的最大连续子段和，即 $\max_{x \le l \le r \le y}\{ \sum_{i=l}^{r} A[i] \}$
2. 2 x y，把 $A[x]$ 改成 $y$。

对于每个查询指令，输出一个整数表示答案。

输入格式

第一行两个整数 $N,M$。

第二行 $N$ 个整数 $A[i]$。

接下来 $M$ 行每行 $3$ 个整数 $k,x,y$，$k=1$ 表示查询（此时如果 $x>y$，请交换 $x,y$），$k=2$ 表示修改。

输出格式

对于每个查询指令输出一个整数表示答案。

每个答案占一行。

数据范围

$N \le 500000, M \le 100000$,

$-1000 \le A[i] \le 1000$

输入样例：

5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 3 2

输出样例：

2
-1

解题

方法一：线段树

思路

单点修改，区间查询，显然需要使用线段树。

然后考虑每个节点需要维护哪些值：

• 首先，题目所求内容 —— 区间最大连续子段和（下称 $mx$）是必然要维护的；

• 接下来考虑是否能由两个子节点的 $l[mx], r[mx]$ 更新维护父节点的 $u[mx]$ ？

  • 不能，因为：

    $$u[mx] = \max\begin{cases} l[mx] \\ r[mx] \\ l[最大后缀子段和] + r[最大前缀子段和] \end{cases}$$

  • 其中，$l[mx], r[mx]$ 都能得到，但当左右子区间被合并起来的时候可能会产生一个和比他俩都要大的合并区间，其和为：$l[最大后缀子段和] + r[最大前缀子段和]$。
    
  • 所以还要另外维护：最大前缀子段和（下称 $lmx$）与最大后缀子段和（下称 $rmx$）。

• 这还不够，还需要考虑是否能由两个子节点的 $l[lmx],l[rmx],r[lmx],r[rmx]$ 更新维护父节点的 $u[lmx],[rmx]$ ？

  • 不能，因为：

    $$\begin{aligned} u[lmx] &= \max(l[lmx], l[区间和] + r[lmx]) \\ u[rmx] &= \max(r[rmx], r[区间和] + l[rmx]) \end{aligned}$$

  • 显然，需要另外维护：区间和（下称 $sum$）。
    

• 最后，考虑是否能由两个子节点的 $l[sum], r[sum]$ 更新维护父节点的 $u[sum]$ ？

  • 可以。

综上，每个节点需要维护四个信息：$mx, lmx, rmx, sum$。

后面就像正常线段树的题直接做即可。

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 5e5 + 10;
int n, m;
int a[N];
struct Node {
    int l, r;
    // 最大连续子段和 最大前缀子段和 最大后缀子段和 区间和
    int mx, lmx, rmx, sum;
    
    void set(int x) {
        mx = lmx = rmx = sum = x;
    }
} tr[N * 4];

void push_up(Node& u, Node& l, Node& r) {
    u.sum = l.sum + r.sum;
    u.lmx = max(l.lmx, l.sum + r.lmx);
    u.rmx = max(r.rmx, r.sum + l.rmx);
    u.mx = max(max(l.mx, r.mx), l.rmx + r.lmx);
}

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

void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if (l == r) tr[u].set(a[l]);
    else {
        int m = l + r >> 1;
        build(u << 1, l, m);
        build(u << 1 | 1, m + 1, r);
        push_up(u);
    }
}

void modify(int u, int i, int x) {
    if (tr[u].l == i && tr[u].r == i) tr[u].set(x);
    else {
        int m = tr[u].l + tr[u].r >> 1;
        if (m >= i) modify(u << 1, i, x);
        else modify(u << 1 | 1, i, x);
        push_up(u);
    }
}

Node query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u];
    int m = tr[u].l + tr[u].r >> 1;
    if (m >= r) return query(u << 1, l, r);
    else if (m + 1 <= l) return query(u << 1 | 1, l, r);
    else {
        Node res;
        Node ln = query(u << 1, l, r), rn = query(u << 1 | 1, l, r);
        push_up(res, ln, rn);
        return res;
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    build(1, 1, n);
    while (m--) {
        int k, x, y;
        scanf("%d%d%d", &k, &x, &y);
        if (k == 1) {
            if (x > y) swap(x, y);
            printf("%d\n", query(1, x, y).mx);
        } else modify(1, x, y);
    }

    return 0;
}