1. 从一道题说起区间最大子段和到底难在哪线段树配上区间最大子段和算是数据结构里一个经典的组合技题目。我第一次遇到它的时候第一反应是最大子段和不是有 O(n) 的 DP 吗一个循环就能解决的事为什么非要套个线段树上去后来才明白问题根本不在算一次而在于边算边改、边改边问——数组里的元素会被单点修改同时要回答任意区间内的最大子段和。这时候 O(n) 的 DP 每次查询都跑一遍配合 m 次询问就直接是 O(nm)n 和 m 都到 1e5 量级的话稳稳超时。所以要解决的问题定义很清晰给定一个长度为 n 的数组支持两种操作——把某个位置的值改成 v查询区间 [l, r] 内所有连续子段中和最大的那个值。注意连续和非空这两个约束它们决定了后面的所有细节。适合谁看如果你已经会写基础的线段树建树、单点修改、区间最值/区间求和但对维护一个能合并的复合信息还没形成感觉这篇正好可以当成从单值维护跨到结构体维护的过渡案例。为什么这个题值得单独拿出来讲因为它是信息扩容思路的最佳教学样本。很多人以为最大子段和没法用线段树维护理由是两个区间的最大子段和没法拼出整体的最大子段和——这句话只对了一半。单个 tmax 确实拼不出来但如果你愿意多存三个量整件事就豁然开朗了。这种为了让信息可合并主动增加维护维度的思维在后面做线段树合并、做树上问题、做扫描线时都会反复用到属于一招通吃的基本功。我们从最直白的地方切入假如数组是 [1, -2, 3, 4, -1, 2, -5, 3]问区间 [2, 6]即 -2, 3, 4, -1, 2的最大子段和是多少。目测答案是 34-12 8。但如果问的是 [1, 8]答案会变成 34-12 8 还是 1-234-12 7要现场手算就有点烦了。而这还只是一次查询。真实场景里是十万次查询叠十万次修改手算和暴力都不现实我们需要一个每步都对数级别、且能稳定合并的结构。2. 节点信息设计四个量撑起整个结构2.1 sum、lmax、rmax、tmax 各自的职责线段树的每个节点对应数组的一段连续区间。在做区间和的时候节点只存一个 sum 就够但在最大子段和这里光有 sum 不够用因为最大这个操作和求和这个操作没法互相推导。我们的做法是让每个节点同时维护四个量sum表示这段区间的元素总和lmax表示这段区间内所有前缀必须以区间左端点开头的最大和rmax表示所有后缀必须以区间右端点结尾的最大和tmax表示这段区间内所有连续子段的最大和也就是我们最终要回答的答案。用一个生活化的类比把区间想象成一条街上的店铺sum 是这条街所有店铺的净利润总和lmax 是从左往头数连续开着的店铺能带来的最大收益rmax 是从右往头数的版本tmax 则是整条街上任意一段连续店铺的最大收益。单独看 tmax你会觉得它和邻居的 tmax 没法定量拼接但有了 lmax 和 rmax 这两个接口拼接就有了抓手。关键点在于这四个量对同一个区间是自洽的任意一个都能由子节点拼出来。这也正是线段树能维护它的前提——父节点的信息必须能完全由两个子节点的信息推导不然 pushup 就无从下手。设计节点信息的时候第一件事永远是问自己我需要哪些量才能让合并式封闭2.2 为什么这四个量刚好够用而不是三五个有人会想能不能少存一个比如把 sum 省掉不行。合并 lmax 和 rmax 的时候要用到 sum父区间的最大前缀要么完全落在左子区间里左.lmax要么吃掉整个左子区间再往右延伸左.sum 右.lmax。没有 sum 这个量第二种情况就没法算。那能不能省掉 rmax只留 lmax也不行因为跨越中点的最大子段是左区间的后缀 右区间的前缀后缀信息必须由 rmax 提供lmax 在这件事上帮不上忙。四个量之间是相互咬合的缺一个合并式就断链。反过来说也不需要更多。比如加个最小子段和那是另一类问题的需求加个区间长度对纯最大子段和而言没有用武之地。判定够不够的标准只有一个把所有需要区分的边界情况列出来看它们能否只用现有量表达。最大子段和的所有情况无非三种——全在左、全在右、跨中点——四种量刚好把第三种也覆盖住。提示节点信息的设计没有标准答案但有标准流程。先写合并式写到最后发现缺什么量就补什么量补到合并式闭合为止。这比拍脑袋列一堆量要靠谱得多也能避免维护一堆用不上的信息拖慢常数。3. pushup 合并式逐项推导3.1 四条公式是怎么推出来的设左子节点为 L右子节点为 R父节点为 P。合并式一共四条逐条来推。第一条P.sum L.sum R.sum。这个最直白总和就是两半相加。第二条P.lmax max(L.lmax, L.sum R.lmax)。父区间的最大前缀只有两种可能完全落在左区间内答案是 L.lmax或者跨过中点进入右区间此时必然包含左区间的全部元素再拼上右区间的某个前缀取最大就是 L.sum R.lmax。取两者较大值即可。第三条P.rmax max(R.rmax, R.sum L.rmax)。和第二条对称注意主体换成了右区间所以是 R.sum 加上左区间的后缀 L.rmax别把顺序写反。第四条P.tmax max(max(L.tmax, R.tmax), L.rmax R.lmax)。父区间的最大子段有三种可能整段在左、整段在右、跨中点。前两种直接取子节点的 tmax第三种必然是左区间的某个后缀 右区间的某个前缀而要让这个和最大后缀和前缀得各自取最大也就是 L.rmax R.lmax。这里有个容易理解的直觉跨越中点的子段一定是贴着中点的左边必须顶到右边界的某个后缀右边必须顶到左边界的某个前缀中间不能断。这四条式子里最反直觉的是第四条里为什么用 rmax lmax 而不是别的组合。你可以这样想任何跨越中点的合法子段都恰好是左区间的后缀和右区间的前缀的并集而这两种形态的最大值分别是 rmax 和 lmax由于两者相互独立、互不影响直接相加就得到了这类子段的最优解。这个独立性是成立的因为后缀和前缀的选择不会互相约束。3.2 单点初始化与边界的正确性叶子节点是最基本的单位它对应的区间只有一个元素 val。此时sum lmax rmax tmax val。四个量全都等于这个值因为对于单元素区间而言总和最大前缀最大后缀最大子段都只能取这个元素本身。这个初始化看起来平凡但它决定了整棵树在递归底部是否正确。这里必须强调一个实战里经常翻车的点题目通常要求子段非空。也就是说即便数组全是负数答案也必须是那个最大的单个负数而不是 0。如果你在初始化时把 lmax、rmax、tmax 设成了 0那么合并时这些 0 会污染结果最后会输出一个 0答案就错了。所以单点初始化一定要老老实实用 val 本身不能想当然地取 max(0, val)。注意这四条公式我第一次写的时候把第四条写成了L.tmax R.tmax还理直气壮地觉得最大值加最大值肯定最大。实测直接错因为最大子段和不是简单叠加两个正的最大值拼起来可能恰好跨越了负的中段反而不如别的组合。合并式必须逐项对应全左、全右、跨中三种情况不能凭感觉。4. 代码落地建树、修改、查询完整实现4.1 建树与单点修改的标准写法建树是标准的递归模板。用数组模拟线段树节点 p 的左儿子是 2p右儿子是 2p1数组开 4n 保险。递归到叶子直接初始化单点回溯时用 merge 函数合并两个儿子。单点修改也类似递归找到对应叶子改成新值回溯时沿途重新 pushup。这两个操作几乎是所有线段树题的通用骨架把 merge 换成你的合并逻辑就能直接复用。const int MAXN 100005; const int NEG -0x3f3f3f3f; // 约 -1.06e9后续会解释为什么用它 struct Node { int sum; // 区间和 int lmax; // 最大前缀和 int rmax; // 最大后缀和 int tmax; // 最大子段和 }; int a[MAXN]; Node tree[MAXN 2]; Node merge(const Node L, const Node R) { Node res; res.sum L.sum R.sum; res.lmax std::max(L.lmax, L.sum R.lmax); res.rmax std::max(R.rmax, R.sum L.rmax); res.tmax std::max(std::max(L.tmax, R.tmax), L.rmax R.lmax); return res; } Node make_node(int val) { Node res; res.sum res.lmax res.rmax res.tmax val; return res; } void build(int p, int l, int r) { if (l r) { tree[p] make_node(a[l]); return; } int mid (l r) 1; build(p 1, l, mid); build(p 1 | 1, mid 1, r); tree[p] merge(tree[p 1], tree[p 1 | 1]); } void update(int p, int l, int r, int x, int v) { if (l r) { tree[p] make_node(v); return; } int mid (l r) 1; if (x mid) update(p 1, l, mid, x, v); else update(p 1 | 1, mid 1, r, x, v); tree[p] merge(tree[p 1], tree[p 1 | 1]); }代码里用了关系的 max 调用命名空间统一用std::max避免写using namespace std带来的一些命名冲突虽然竞赛里一般无所谓。MAXN 2就是 4 倍这是线段树数组的常用上界原因是递归划分的节点总数不会超过 4n别省这个量省了就等着数组越界。4.2 区间查询返回值必须是一个结构体区间查询是整个题最容易写错的地方因为查询区间可能横跨左右子树也可能只落在一侧。经典的写法是让查询函数直接返回一个 Node如果查询区间完全覆盖当前节点直接把tree[p]返回如果只和左儿子相交递归左儿子如果只和右儿子相交递归右儿子如果两边都相交就分别查左右再 merge。Node query(int p, int l, int r, int ql, int qr) { if (ql l r qr) return tree[p]; int mid (l r) 1; if (qr mid) return query(p 1, l, mid, ql, qr); if (ql mid) return query(p 1 | 1, mid 1, r, ql, qr); Node L query(p 1, l, mid, ql, qr); Node R query(p 1 | 1, mid 1, r, ql, qr); return merge(L, R); }这个版本的好处是不存在空区间。因为只要查询区间和当前节点有交那么递归下去要么整个落在左半边要么整个落在右半边要么真的两边都要。三个分支互斥且完备不会出现左半边返回空、需要特殊处理的情况。很多朋友写查询喜欢先递归两边再 merge结果遇到空区间就不知道怎么合了还要专门构造一个空节点去兜底代码一下子复杂起来。三分支写法直接把这个问题消灭在源头。给一个调用示例读入 ql、qr 之后Node ans query(1, 1, n, ql, qr);然后输出ans.tmax即可。注意建树时区间是 [1, n]所以数组从下标 1 开始存这也是竞赛里的惯例。4.3 完整可编译模板把上面的片段拼起来加上输入输出就是一个可以直接提交的程序。#include cstdio #include algorithm const int MAXN 100005; struct Node { int sum, lmax, rmax, tmax; }; int a[MAXN]; Node tree[MAXN 2]; Node merge(const Node L, const Node R) { Node res; res.sum L.sum R.sum; res.lmax std::max(L.lmax, L.sum R.lmax); res.rmax std::max(R.rmax, R.sum L.rmax); res.tmax std::max(std::max(L.tmax, R.tmax), L.rmax R.lmax); return res; } Node make_node(int val) { Node res; res.sum res.lmax res.rmax res.tmax val; return res; } void build(int p, int l, int r) { if (l r) { tree[p] make_node(a[l]); return; } int mid (l r) 1; build(p 1, l, mid); build(p 1 | 1, mid 1, r); tree[p] merge(tree[p 1], tree[p 1 | 1]); } void update(int p, int l, int r, int x, int v) { if (l r) { tree[p] make_node(v); return; } int mid (l r) 1; if (x mid) update(p 1, l, mid, x, v); else update(p 1 | 1, mid 1, r, x, v); tree[p] merge(tree[p 1], tree[p 1 | 1]); } Node query(int p, int l, int r, int ql, int qr) { if (ql l r qr) return tree[p]; int mid (l r) 1; if (qr mid) return query(p 1, l, mid, ql, qr); if (ql mid) return query(p 1 | 1, mid 1, r, ql, qr); Node L query(p 1, l, mid, ql, qr); Node R query(p 1 | 1, mid 1, r, ql, qr); return merge(L, R); } int main() { int n, m; scanf(%d%d, n, m); for (int i 1; i n; i) scanf(%d, a[i]); build(1, 1, n); while (m--) { int op, x, y, v; scanf(%d, op); if (op 0) { // 单点修改a[x] v scanf(%d%d, x, v); update(1, 1, n, x, v); } else { // 区间查询[x, y] 的最大子段和 scanf(%d%d, x, y); printf(%d\n, query(1, 1, n, x, y).tmax); } } return 0; }这份代码可以直接拿去跑最大子段和的标准题建树 O(n)每次修改和查询都是 O(log n)。实测下来 n、m 到 1e5 规模运行时间在几十毫秒量级非常稳。如果你的数据到 2e5把 MAXN 调大即可其它不用动。5. 查询合并顺序与常见坑速查5.1 左右顺序颠倒会出什么错前面第四条合并式里L.rmax R.lmax这个顺序是有讲究的交换成L.lmax R.rmax就错了。原因在于跨越中点的子段左边部分必须是贴着中点的后缀右边部分必须是贴着中点的前缀。如果把 L 和 R 的位置调换那么语义就变成了左区间的前缀 右区间的后缀这两部分在位置上根本不连续拼出来的不是合法子段结果自然离谱。查询的时候也要特别注意顺序。三分支写法里先查左再查右merge 的时候把左结果放第一个参数、右结果放第二个参数这个顺序和数组的物理顺序一致不会出问题。但如果有人为了省事写成先合并右边再合并左边就会出现 rmax 和 lmax 用反的 bug。这类 bug 很隐蔽因为小数据下可能凑巧过大数据才炸。我的习惯是在 merge 函数里加注释明确标注哪个参数是左、哪个是右隔一段时间回看也不会混。另外提醒一句如果你选择用空节点方案处理查询即允许返回一个无效区间再和有效结果合并那个空节点的构造也得和顺序配合好。空节点通常设成sum 0, lmax rmax tmax NEG这样和有效节点合并时才会被吸收掉。NEG 要选足够小的负数但又要保证相加不溢出 int。用 -0x3f3f3f3f约 -1.06e9是稳妥的选择两个 -0x3f3f3f3f 相加约 -2.12e9刚好在 int 范围内int 下限约 -2.147e9不会溢出。如果用 -1e9两两相加就可能越界。这个负无穷取值的细节在竞赛里是常识但自己写的时候确实容易忽略。5.2 常见错误现象对照表把实战里踩过和见过的问题整理成一张表方便对照排查。错误现象可能原因排查方法全负数数据输出 0初始化 lmax/rmax/tmax 时取了 max(0, val)检查make_node叶子必须等于 val部分查询结果偏小merge 里 tmax 漏掉L.rmax R.lmax这一项对照四条合并式逐项核对结果偏大或为奇怪正数空节点 tmax 设成了 0污染了合并空节点 tmax 用 NEG或改用三分支查询跨中点查询结果错误合并时左右参数顺序颠倒确认 merge(左, 右) 的实参顺序数组越界、程序崩溃线段树数组只开了 2n 或 n开到MAXN 2大数据超时查询里反复值拷贝大结构体加引用传参或改用更紧凑的写法单点修改后查询不变update 递归后忘了 pushup检查递归返回后是否重新 merge这张表里的每一条都是真实会遇到的。尤其是第一条和第三条全负数据和空节点污染堪称这个题型的两大新手杀手。全负数据的坑在于测试用例往往都是正负数混合的本地手测根本发现不了直到提交才 WA。而空节点污染的问题我见过不止一个人栽在上面原因就是构造空节点时想当然地认为空的和就是 0那最大值也取 0 吧结果全负区间被这个 0 顶掉。提示调试这类问题时建议手写一个小数据暴力程序随机生成 n ≤ 10 的数组和若干操作把线段树的输出和暴力答案逐条对比。这种对拍方法能在几分钟内定位出绝大多数逻辑错误比盯着代码发呆高效得多。6. 变形与扩展从单点修改到更复杂的版本6.1 带单点修改和区间限制的版本单点修改的版本就是上面的模板直接套用。稍微进阶一点的是查询带左右端点限制的版本给定两段区间 [l1, r1] 和 [l2, r2]保证 l1 ≤ l2r1 ≤ r2要求选一个子段 [x, y]满足 x 在 [l1, r1]、y 在 [l2, r2] 且 x ≤ y求这个子段的最大和。这类问题需要按两段区间的相对位置分类讨论大概分成两段不重叠两段部分重叠等几种情况每种情况用不同的查询组合拼出答案。分类讨论的时候你会用到之前维护的 lmax、rmax、tmax 的不同组合。比如两段完全分离时答案就是左段的后缀 中间整段 右段的前缀两段有重叠时又要细分。虽然讨论起来有点繁琐但核心还是那四个量的拼接。这类题目的价值在于逼你真正理解 rmax 和 lmax 的语义因为在分类讨论里你必须清楚地知道我要的是贴着右边界的后缀还是贴着左边界的后缀一旦概念模糊就没法下手。6.2 区间加为什么会让问题突然变难有人会问如果是区间整体加一个值呢这个问题就没那么简单了。单点修改时叶子节点的四个量直接变成新值即可其余节点 pushup 一次就能修正。但区间加不同给一个区间整体加 k这个区间的 sum 会增加 k 乘以区间长度但 lmax、rmax、tmax 却不是简单加上 k 乘以长度因为最大前缀/子段可能只取了区间的一部分加的 k 只会作用在它覆盖的那部分长度上而到底是多长节点里并没有直接记录。要正确处理区间加下的最大子段和通常需要额外维护最长前缀的长度之类的信息或者干脆放弃线段树改用分块之类的结构。这也是为什么主流的最大子段和题目大多设计成单点修改而不是区间加。认识到这一点很重要不是所有信息都能在线段树上优雅地叠加 lazy 标记判断一个操作能否 lazy 化的标准就是看它对节点信息的影响能不能用常数个参数描述。区间的加法对 sum 可以对 tmax 就不行。6.3 其他解法与实际选型参考除了线段树这类问题还有别的解法各有适用场景。如果完全没有修改操作只有一堆静态查询那可以离线处理或者用分治类似 CDQ 分治的思路把查询挂到区间上复杂度也是 O((n m) log n)。如果只需要求整个数组的最大子段和那 O(n) 的 DP 是最好用的两个变量滚动一下就行根本不用线段树。如果需要求的是和最大的子段且长度不超过 k那又是另一套单调队列加前缀和的解法。选型的判断其实很简单看有没有修改、查询是不是任意区间。有单点修改、任意区间查询线段树是首选纯静态查询可以离线但线段树写起来反而更省心不必为了那点常数去折腾复杂的分治。至于分块在 n 到 1e5 这个量级上块长取 sqrt(n) 大约 300 多查询是 O(sqrt(n))比线段树慢一个量级一般只在 lazy 标记难以维护时才会退而求其次。我个人的习惯是只要线段树能写明白就优先线段树除非复杂度确实不允许。最后分享一个我自己的练习方法把这份模板敲熟之后试着不看书默写一遍尤其是 merge 的四条式子。默写的时候特别注意两个地方一是 tmax 那条有没有漏掉跨界项二是 rmax 的式子里到底该用 L 还是 R。写完拿小数据对拍能全过说明你真的理解了而不是背下来了。这个题看着简单但它是线段树从维护单值进阶到维护结构体的分水岭把这关过了后面做更复杂的区间信息合并会顺很多。我自己在这一题上前后踩了三次坑才把四个量的关系彻底捋清希望你不用重复走这些弯路。