形式化题目

给定长度为 $N$ 的数列 $A_1, A_2, \ldots, A_N$，需要在线处理 $M$ 条指令， 指令只有两种：

• 查询：给出 $x, y$，求 $\displaystyle \max_{l \leqslant i \leqslant j \leqslant r}\ \sum_{t=i}^{j} A_t$， 其中 $l = \min(x, y)$、$r = \max(x, y)$；
• 修改：给出 $x, y$，令 $A_x \leftarrow y$。

注意子段必须非空：$i \leqslant j$，所以当区间内全是负数时， 答案是该区间内的最大单元素值，而不是 $0$。

暴力解法

思路

约束是 $N \leqslant 500000$、$M \leqslant 100000$、$|A_i| \leqslant 1000$，时限 1 秒。 先看最朴素的做法：查询就是「最大连续子段和」的经典问题，扫一遍用 Kadane 在线求出：

1
2
3
4best = -inf ; cur = -inf
for v in A[l..r]:
    cur  = max(v, cur + v)    # 要么从 v 重新开始, 要么把 v 接到前面
    best = max(best, cur)

初值取 $-\infty$ 而不是 $0$，保证选出的子段非空。

代码

复杂度

• 时间：一次查询 $O(r - l + 1)$，$M$ 次查询合计 $O\!\left(\sum (r - l + 1)\right)$，最坏 $O(NM) = 5 \times 10^{10}$ 次加法。
• 空间：$O(1)$ 额外空间（不算原数组）。

瓶颈

慢只是表象，真正的瓶颈是区间答案不可合并：

因为最优子段可能跨越中缝 $m$，它的一部分在左半、一部分在右半。 正因如此，$\text{best}$ 既不能做前缀和相减，也不能直接挂到线段树上。 要提速，必须先想办法把「区间答案」补齐成可合并的信息。

正解

思路

第一步：给区间补上两个贴边的量

跨越中缝的子段一定形如「左段的一个后缀 + 右段的一个前缀」。于是我们对每个区间 $[l, r]$ 记录四元组：

pre 和 suf 的「贴边」约束不是装饰：只有贴着边，两块拼起来才是连续的一段。

第二步：写出合并式

设左段 $L$、右段 $R$，则

以 pre 为例：贴着左端的前缀要么没越过中缝（最优是 $L.\text{pre}$）， 要么整段吃掉 $L$ 再加 $R$ 的一个前缀（最优是 $L.\text{sum} + R.\text{pre}$）。 best 的第三项 $L.\text{suf} + R.\text{pre}$ 正是「跨越中缝」的最优解。 四个量互相封闭——合并结果仍然只需要这四个量，不依赖区间长度，所以这个运算可以 在树上任意嵌套。

用样例 $A = [1, 2, -3, 4, 5]$ 按 main.py 的补位方式补到 8 个叶子，自底向上逐层算出的 四元组如下（数字由 problem-analysis-workspace/viz_render.py 打印，与代码一致）：

叶子的四元组全是同一个数 $a_i$：单元素区间的 sum、pre、suf、best 都只能是它本身。最底层多出来的三个「补位叶」填 0，它们占据的整块区间都超出 $[1,5]$，任何查询都选不到，所以填什么都不会影响答案。倒数第二层里，节点 $[3,4]$ 的 $\text{pre}=1$ 而 $\text{suf}=4$：贴左的前缀最优是 $-3+4$，贴右的后缀最优是 $4$，同一个区间里两个贴边量可以完全不同，这正是「贴边」含义的直接体现。

第三步：搬进线段树

线段树只要满足「任意区间的答案 = 覆盖它的那些节点依次合并」，而上面的合并式满足 结合律，于是：

• 建树：叶子填 $(A_i, A_i, A_i, A_i)$，内部节点自底向上 push up。 叶子层长度补到 $\geqslant N$ 的最小 $2$ 的幂 $B$；补位叶子填四元组 $(0,0,0,0)$， 因为它所在的整块区间都超出 $[1, N]$，任何查询都选不到它。
• 修改：改叶子后沿父链 push up，$O(\log N)$。
• 查询：把 $[l, r)$ 自底向上拆成 $O(\log N)$ 个节点。

第四步：查询的左右两个暂存区

自底向上分解时，收下的节点会分别属于两个方向：左端点决定「左暂存区」， 右端点决定「右暂存区」。下面是样例数组补到 8 个叶子后的线段树区间划分 （$[6,6]$、$[7,7]$、$[8,8]$ 是补位叶，它们不参与任何答案）：

查询 $[2, 5]$ 时依次收下 $[2,2]$、$[5,5]$、$[3,4]$ 三个节点，推演过程是：

1
2
3
4左吞 [2,2] → 左暂存区 sum=2  pre=2  suf=2  best=2
右吞 [5,5] → 右暂存区 pre=5  best=5
左吞 [3,4] → 左暂存区 sum=3  pre=3  suf=4  best=4
收尾        → max(best=5, lu+rp=9) = 9

左暂存区吞下的顺序是 $[2,2]$、$[3,4]$，说明自底向上分解给出的节点一定是 从左到右排列的；左暂存区的 suf 变成 4，是因为它贴着右侧的 $[3,4]$ 全取了。 最后 $lu + rp = 4 + 5 = 9$ 把两段连起来，正好对应子段 $A_4 + A_5$。

关键在于左暂存区整体在右暂存区左边、不能调换顺序：要合并两块必须写成 $L$ 在前、$R$ 在后。而合并结果的 $\text{best}$ 恰好只用到三项，即 「左段的 best」「右段的 best」「跨越中缝的 $L.\text{suf} + R.\text{pre}$」， 所以收尾不需要真的构造出完整四元组：

上面那次查询里 $L.\text{suf} = 4$（对应 $[3,4]$，正好贴着左暂存区右端）、 $R.\text{pre} = 5$，交叉项 $9$ 就是 $4 + 5$。

用题面样例把整条输出对一遍：

后一行说明了两件事：$x > y$ 必须先交换；当区间全为负数时，答案只能是 「贴边的单个元素」$-1$（$\text{best}$ 用 $L.\text{best} = -1$ 胜出， 交叉项 $-4$ 落选）。若允许空段，这里会错误地输出 $0$。

把节点 $C$ 并入暂存区时必须用旧值，两侧都一样：

1
2
3
4
5
6
7# C 并入左暂存区（C 在暂存区右边）
new_suf  = max(C.suf,  C.sum + old_suf)
new_best = max(old_best, C.best, old_suf + C.pre)   # 这里也是 old_suf

# C 并入右暂存区（C 在暂存区左边）
new_pre  = max(C.pre,  C.sum + old_pre)
new_best = max(old_best, C.best, C.suf + old_pre)   # 同理用 old_pre

若先更新了 suf（或 pre）再用新值算 best，交叉项就变成「两段的后缀拼在一起」 （或「两段的前缀拼在一起」），区间中部的元素会被重复计入，答案偏大。 代码里用局部变量 u（左）和 p（右）先存下旧值，就是为了这个。

最后，$x > y$ 时先交换再查询；子段非空由叶子值和初值 $-\infty$ 共同保证—— 暂存区空的时候 $\text{best}$ 取 $-\infty$，所以它永远不会冒充一个真实答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
// GSS：线段树维护 sum / pre / suf / best 四元组，迭代式建树、查询与单点修改。
#include <cstdio>

typedef long long ll;

const ll MAXB = 1 << 19; // 叶子层长度上限（n ≤ 5e5）
const ll NEG = -(1LL << 60); // 空区间的最大子段和

struct Node {
    ll sum;  // 区间和
    ll pre;  // 最大前缀和
    ll suf;  // 最大后缀和
    ll best; // 最大子段和
};

Node t[2 * MAXB];
ll base; // 叶子层长度（≥ n 的最小 2 的幂）

// 由左右孩子重算 p 的四个量
void pull(ll p) {
    ll a = p << 1;
    ll s1 = t[a].sum, p1 = t[a].pre, u1 = t[a].suf, b1 = t[a].best;
    ll s2 = t[a + 1].sum, p2 = t[a + 1].pre, u2 = t[a + 1].suf, b2 = t[a + 1].best;
    t[p].sum = s1 + s2;
    ll x = s1 + p2;
    t[p].pre = p1 > x ? p1 : x; // pre = max(左 pre, 左 sum + 右 pre)
    x = s2 + u1;
    t[p].suf = u2 > x ? u2 : x; // suf = max(右 suf, 右 sum + 左 suf)
    ll b = b1 > b2 ? b1 : b2;
    x = u1 + p2;
    t[p].best = b > x ? b : x; // best = max(左 best, 右 best, 左 suf + 右 pre)
}

// 区间最大连续子段和：把 [l, r) 拆成若干节点，分左右两段归并
ll query(ll l, ll r) {
    l += base;
    r += base;
    ll ls = 0; // 左暂存区的 sum，按「空区间」起步
    ll lp = NEG, lu = NEG, lb = NEG, rp = NEG, rb = NEG;
    while (l < r) {
        if (l & 1) {
            ll u = lu; // 先存旧 suf：合并式里必须用归属左段的旧值
            ll x = ls + t[l].pre;
            lp = lp > x ? lp : x;
            x = t[l].sum + u;
            lu = t[l].suf > x ? t[l].suf : x;
            x = u + t[l].pre;
            ll b = lb > t[l].best ? lb : t[l].best;
            lb = b > x ? b : x;
            ls += t[l].sum;
            l++;
        }
        if (r & 1) {
            r--;
            ll p = rp; // 同理，先存旧 pre
            ll x = t[r].sum + p;
            rp = t[r].pre > x ? t[r].pre : x;
            x = t[r].suf + p;
            ll b = rb > t[r].best ? rb : t[r].best;
            rb = b > x ? b : x;
        }
        l >>= 1;
        r >>= 1;
    }
    ll b = lb > rb ? lb : rb; // 左暂存区在右、右暂存区在左，只有跨界的 lu+rp 相连
    ll x = lu + rp;
    return b > x ? b : x;
}

// 单点修改：改写叶子，再沿父链逐层重新合并
void update(ll i, ll v) {
    ll c = base + i;
    t[c].sum = t[c].pre = t[c].suf = t[c].best = v;
    c >>= 1;
    while (c) {
        pull(c);
        c >>= 1;
    }
}

int main() {
    ll n, m;
    if (scanf("%lld %lld", &n, &m) != 2) return 0; // 空输入安全返回

    base = 1;
    while (base < n) {
        base <<= 1;
    }

    for (ll i = 0; i < n; i++) {
        ll v;
        scanf("%lld", &v);
        t[base + i].sum = t[base + i].pre = t[base + i].suf = t[base + i].best = v;
    }
    // 补位叶子仍是 0，但它所在的整块区间都超出 [0, n)，查询永远选不到
    for (ll p = base - 1; p >= 1; p--) {
        pull(p);
    }

    for (ll q = 0; q < m; q++) {
        ll k, x, y;
        scanf("%lld %lld %lld", &k, &x, &y);
        if (k == 1) {
            if (x > y) {
                ll tmp = x;
                x = y;
                y = tmp;
            }
            printf("%lld\n", query(x - 1, y));
        } else {
            update(x - 1, y);
        }
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 17:53
# update_at: 2026-10-01 18:04

import sys
from array import array
from collections.abc import Iterator

NEG = -(1 << 60)  # 空区间的最大子段和；合法答案不小于 -1000*5e5，这里远比它小


def build_leaves(t: memoryview, data: Iterator[int], n: int, base: int) -> None:
    """写叶子和内部节点，自底向上建树。"""
    for i in range(n):
        c = (base + i) << 2
        v = next(data)
        t[c] = t[c + 1] = t[c + 2] = t[c + 3] = v
    for p in range(base - 1, 0, -1):
        c = p << 2
        a = p << 3  # 左孩子 2p 的槽位起点
        s1, p1, u1, b1 = t[a], t[a + 1], t[a + 2], t[a + 3]
        s2, p2, u2, b2 = t[a + 4], t[a + 5], t[a + 6], t[a + 7]
        t[c] = s1 + s2
        x = s1 + p2
        t[c + 1] = p1 if p1 > x else x  # pre = max(左 pre, 左 sum + 右 pre)
        x = s2 + u1
        t[c + 2] = u2 if u2 > x else x  # suf = max(右 suf, 右 sum + 左 suf)
        b = b1 if b1 > b2 else b2
        x = u1 + p2
        t[c + 3] = b if b > x else x  # best = max(左 best, 右 best, 左 suf + 右 pre)


def query(t: memoryview, base: int, l: int, r: int) -> int:
    """区间最大连续子段和：把 [l, r) 拆成若干节点，分左右两段归并。"""
    l += base
    r += base
    ls = 0  # 左暂存区的 sum，按"空区间"起步，所以是 0
    lp = lu = lb = rp = rb = NEG  # 两侧贴边量与空区间初值；右暂存区只留 pre/best
    while l < r:
        if l & 1:
            c = l << 2
            u = lu  # 先存旧 suf：合并式里必须用归属左段的旧值
            x = ls + t[c + 1]
            lp = lp if lp > x else x
            x = t[c] + u
            lu = t[c + 2] if t[c + 2] > x else x
            x = u + t[c + 1]
            b = lb if lb > t[c + 3] else t[c + 3]
            lb = b if b > x else x
            ls += t[c]
            l += 1
        if r & 1:
            r -= 1
            c = r << 2
            p = rp  # 同理，先存旧 pre
            x = t[c] + p
            rp = t[c + 1] if t[c + 1] > x else x
            x = t[c + 2] + p
            b = rb if rb > t[c + 3] else t[c + 3]
            rb = b if b > x else x
        l >>= 1
        r >>= 1
    b = lb if lb > rb else rb  # 左暂存区在右、右暂存区在左，只有跨界的 lu+rp 相连
    x = lu + rp
    return b if b > x else x


def update(t: memoryview, base: int, i: int, v: int) -> None:
    """单点修改：改写叶子，再沿父链逐层重新合并。"""
    c = (base + i) << 2
    t[c] = t[c + 1] = t[c + 2] = t[c + 3] = v
    p = (base + i) >> 1
    while p:
        c = p << 2
        a = p << 3
        s1, p1, u1, b1 = t[a], t[a + 1], t[a + 2], t[a + 3]
        s2, p2, u2, b2 = t[a + 4], t[a + 5], t[a + 6], t[a + 7]
        t[c] = s1 + s2
        x = s1 + p2
        t[c + 1] = p1 if p1 > x else x
        x = s2 + u1
        t[c + 2] = u2 if u2 > x else x
        b = b1 if b1 > b2 else b2
        x = u1 + p2
        t[c + 3] = b if b > x else x
        p >>= 1


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    base = 1 << (n - 1).bit_length()  # 叶子层长度取到 >= n 的 2 的幂
    # 一条线段树节点摊平成 4 个槽位 sum/pre/suf/best；数组按 8*base 个 int64 预留。
    # 补位叶子的 best 仍是 0，但它所在的整块区间都超出 [0, n)，查询永远选不到。
    t = memoryview(array('q', [0]) * (8 * base))

    build_leaves(t, data, n, base)

    out: list[str] = []
    for _ in range(m):
        k, x, y = next(data), next(data), next(data)
        if k == 1:
            if x > y:
                x, y = y, x
            out.append(str(query(t, base, x - 1, y)))
        else:
            update(t, base, x - 1, y)

    sys.stdout.write('\n'.join(out) + '\n')


if __name__ == "__main__":
    solve()

实现说明：

• NEG = -(1 << 60) 是空区间的哨兵。答案最小可能是 $-1000 \times 500000 = -5 \times 10^8$， 比 $-2^{60}$ 大得多，所以 $-\infty$ 不会被真实答案顶替。
• 节点 $p$ 的四个量存在数组槽位 4p, 4p+1, 4p+2, 4p+3（依次为 sum/pre/suf/best）， 左孩子 2p 的起点就是 8p。用 array('q') + memoryview 是为了在 128 MB 内存 限制下存下 $8 \times B$ 个 64 位整数。
• build_leaves 与 update 里的合并式是同一段，各自内联展开而没有抽成函数： 最坏情况 $10^5$ 次修改 $\times 19$ 层，Python 的函数调用开销不可忽略。
• query 收尾那两行没有用暂存区的 sum，因为 $\text{sum}$ 不参与最终答案； 同理右暂存区只需要维护 pre/best 两个量，不需要 suf 和 sum。

复杂度

• 建树 $O(N)$：自底向上处理 $2B - 1$ 个节点。
• 单次修改 $O(\log N)$，单次查询 $O(\log N)$（分解出 $O(\log N)$ 个节点，每次 $O(1)$ 归并）。
• 总计 $O(N + M \log N)$，空间 $O(N)$，与标准 C++ 正解同阶。

总结

• 最大连续子段和不能直接相减或取 $\max$，是因为最优子段可能跨越中缝； 补上贴左的 pre 和贴右的 suf 之后，跨越中缝的候选 $L.\text{suf} + R.\text{pre}$ 就能被显式表达，四元组因此封闭、可结合。
• 有了结合律，单点修改 + 区间查询就落在标准线段树上：修改沿父链 push up， 查询把区间拆成节点后归并。
• 两个容易写错的点：查询的左右暂存区在树上并不相邻，收尾只能取 $\max(\text{best}, L.\text{suf} + R.\text{pre})$；归并时 best 必须用 暂存区的旧 suf/pre，否则中部元素被重复计算。

图示解析

从建模到答案的完整路线：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18            区间最大连续子段和
                    |
                    v
      一个区间只要 4 个量: sum / pre / suf / best
                    |
                    v
      合并: pre  = max(L.pre, L.sum + R.pre)
            suf  = max(R.suf, R.sum + L.suf)
            best = max(L.best, R.best, L.suf + R.pre)
                    |
                    v
            线段树: 叶子 = (a, a, a, a)
                    |
        +-----------+-----------+
        v                       v
  修改: 改叶子            查询: 自底向上拆成若干节点
        沿父链 push up          落进左右两个暂存区
                                max(best, lu + rp)

图中第一层是题目要求的目标；第二层说明「一个区间需要携带哪些信息才能被合并」， 这是全题唯一的建模决定；第三层是三个合并式，其中 best 的第三项来自跨越中缝 的子段；第四层把合并式交给线段树，左边是修改路径，右边是查询路径。 查询末尾的 $\max(\text{best}, \text{lu} + \text{rp})$ 提醒读者： 两个暂存区是有先后顺序的（左段在前、右段在后），而收尾只需要合并结果的 $\text{best}$ 这一项，不必真的拼出完整四元组。