跳到主要内容

线段树：最大子段和

子段：序列中连续的的子序列。

最大子段和：求所有子段中，元素之和的最大值。本文也稍微提一嘴离线做法，但重点在线段树的在线做法。

离线做法：DP，O(n)O(n)​

设 dp[i] 表示第 i 个元素必选，用前 i 个元素得到的最大子段和（或者说以 i 结尾的序列的最大子段和）。直接上代码：

int n;
cin >> n;
for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (i - 1 > 0 and dp[i-1] > 0) // 如果 dp[i-1] 是负的我们就不拼接
    {
        dp[i] = a[i] + dp[i]; // 在前一个元素结尾的序列上，拼接新的 a[i]
    } else {
        dp[i] = a[i];
    }
}

输出答案的时候遍历一遍，也是 O(n)O(n)：

int ans = 0;
for (int i = 0; i < n; i++) {
    ans = max(ans, dp[i]);
}
cout << ans << endl;

在线做法：线段树，O(nlog⁡n)O(n\log n)​

（单点修改，区间查询）

和一般的线段树不一样，这次我们不用 LazyTag\text{LazyTag}（实际上也没法设计 LazyTag\text{LazyTag}）。并且我们参入一点区间 DP、分治法的思想：

考虑：已知左右两个子区间的最大子段和，如何求当前区间的最大子段和？我们发现做不到。因为最大子段和的序列选取有以下几种情况：

1.取ls的前缀
|+++++|
|--------|--------|
2.取ls的子段(或全部)
  |++++|
|--------|--------|
3.取ls的全部、rs的前缀
|+++++++++++|
|--------|--------|
4.取ls的后缀、rs的前缀
     |+++++++|
|--------|--------|
5.取ls的后缀、rs的全部
      |+++++++++++|
|--------|--------|
6.取rs的子段(或全部)
           |++++|
|--------|--------|
7.取rs的后缀
            |+++++|
|--------|--------|

所以我们需要维护以下四个信息，才能维护最大子段和：

  1. 最大前缀和

  2. 最大后缀和

  3. 最大子段和

  4. 区间和

注意下面我们不起名 Node，而是 Segment，可以巧妙地复用一些代码，见 query()。

参考了：题解 P4513 【小白逛公园】 - 洛谷专栏

struct Segment { // 区间/线段
    int pre, suf, sub, sum; // 前缀和、后缀和、子段和、区间和
} nodes[MAXN << 2 | 1];

pushup() 函数传入两个区间 ls、rs（两者的交集是连续的），然后返回这两个区间的数据合并的结果。这样设计在 query() 还有一个妙用。

#define max4(a,b,c,d) max(max(max(a,b),c),d)
Segment pushup(const Segment& ls, const Segment& rs) { // 必须是常量引用
    Segment res;
    res.pre = max(ls.pre, ls.sum + rs.pre);
    res.suf = max(rs.suf, ls.suf + rs.sum);
    res.sum = ls.sum + rs.sum;
    // 最复杂的字段和计算
    res.sub = max(res.pre, res.suf); // 充分利用已知信息
    res.sub = max4(res.sub, ls.sub, rs.sub, ls.suf + rs.pre);
    return res;
}

你可能会问，为什么不写 “res.sub = ls.sum + rs.sum” 的情况？

这种情况下，说明 ls.pre 就是 ls.sum，同时 rs.suf 就是 rs.sum，而我们显然已经考虑过这种情况了。

建树：

void build(int l, int r, int cur) {
    if (l == r) {
        nodes[cur].pre = nodes[cur].suf = nodes[cur].sub = nodes[cur].sum = arr[l];
    } else {
        int m = l + ((r - l) >> 1);
        build(l, m, cur << 1);
        build(m + 1, r, cur << 1 | 1);
        nodes[cur] = pushup(nodes[cur << 1], nodes[cur << 1 | 1]);
    }
}

单线修改（和建树挺类似的）：

void update(int x, int y, int l, int r, int cur) {
    if (l == r) {
        nodes[cur].pre = nodes[cur].suf = nodes[cur].sub = nodes[cur].sum = y;
    } else {
        int m = l + ((r - l) >> 1);
        if (x <= m) update(x, y, l, m, cur << 1);
        else update(x, y, m + 1, r, cur << 1 | 1);
        nodes[cur] = pushup(nodes[cur << 1], nodes[cur << 1 | 1]);
    }
}

查询时这样处理（注意我们返回的 Segment 里面包含了四种和的信息，表示的是『查询区间和当前区间的交集』上的最大前缀和、最大后缀和、……）：

Segment query(int L, int R, int l, int r, int cur) {
    if (L <= l and r <= R) { // 当前区间被覆盖，直接返回
        return nodes[cur];
    }
    int m = l + ((r - l) >> 1);
    if (l <= m and m < r) { // 查询区间跨过了中点
        // 用 pushup() 合并两个区间的信息，从前文的铺垫可知这样是完全可行的
        return pushup(query(L, R, l, m, cur << 1), query(L, R, m + 1, r, cur << 1 | 1));
    }
    if (l <= m) return query(L, R, l, m, cur << 1); // 很好理解，查询区间只交左儿子就只查左儿子
    else return query(L, R, m + 1, cur << 1 | 1);
}