线段树入门

这道题的原型是洛谷 P3372，那道题只有前两条。这里多要了一行「最终的整个数组」。

★ 它和这一章的主题是同一件事：懒标记是欠账，那么题面最后就要求你把账全部还清。 代码里那三行 flush（一路下推到叶子）不是附加题，它是很多题目真正要的东西 （「模拟完之后每个位置是多少」）。

⚠ 这是第 35~38 章那条「题面多问一句，对拍就多一条腿」的第五次现场。 第 37 章给它划过边界（弱数据上格外值钱，数据一狠边际价值就掉）， 第 38 章说清了它兜的是「随机数据碰不到的那个边界」。 这一章的账又复刻了一次，而且这次能说清它兜住的是哪一半：

★★ 弱数据上它把两个 bug 抬了 1.6 倍和 2.5 倍（151 → 238、59 → 150）， 数据够狠之后只值 298 → 300 和 295 → 299。 ★ 而另外五列一个数字都没动 —— 因为末行走的是「一路下推到叶子」那条路， 它只检查账对不对，不检查和算得对不对。

8 10
3 1 4 1 5 9 2 6

2 1 8        → 31       全区间：根节点一个人就答完了
1 3 4 10                ★ [3,4] 正好是一个节点，账记在它头上就走
1 3 4 5                 ★ 同一个节点又来一笔 —— 两笔账要叠起来（15）
2 1 4        → 39       ★ 只读到 [1,4] 那个节点，还没人下推过
1 2 3 100               ★ 这次要从那个欠着账的节点身上**穿过去**
2 4 5        → 21       跨过根的 mid，左右各拼一块
1 5 8 7                 ★ [5,8] 也正好是一个节点
2 6 7        → 25       ★ 钻进 [5,8] 里面 —— 被迫连下推三次
2 1 8        → 289
1 1 8 1                 ★ 整个数组加 1：只碰根节点一格

答案：31 39 21 25 289，末行 4 102 120 17 13 17 10 14。

• 第 2、3 条：[3,4] 恰好是一个节点管的段，两次修改都只碰它一格，账叠成 15；
• 第 5 条是这一章的关键现场：修改要穿过那个欠着 15 的节点， 于是它被迫先把账还给两个儿子；
• 第 8 条 2 6 7 一步连下推三次（[5,8] → [5,6] → [7,8]）；
• 最后一条 1 1 8 1 是「懒」的极致：改整个数组只碰一个节点；
• 而那 8 个数的末行，是把还欠着的每一笔账都推到叶子之后才拿到的。

秒表失灵，那就数次数（第 21 章 stairsCount.cpp 以来的老规矩：次数可复现，秒数不可复现）。

• brute：把数组看成一棵「只有叶子、没有内部节点」的退化结构，碰 a[i] 一次算一格；
• 三棵树：每递归进入一个节点算一格；
• ⚠ fast 还要额外算上 pushdown 对两个儿子的读写（各一格）—— 那两下是实打实动了数据，不算进去这张表就是在给懒标记放水。

点「运行 ▶」看结果

实测（./genBig 20000 20000 档位，n = m = 2×10⁴，全部写进了 check:viz）：

★★ 第一行那三个数字一字不差 —— 这就是「懒标记省了什么」最干净的回答：

区间长度是 1 的时候，它一格都省不了；区间拉到整段，它省 459 倍。 （402 744 320 ÷ 876 724 = 459。）

⚠ 而最后一列（mark，标记永久化）在每一档都比懒标记更便宜 —— 那是第 8 步的事。

区间加 [l,r] += x 的时候，如果某个节点管的那一段整个落在 [l,r] 里面， 那么这一整段每个数都要加 x —— 可我们并不需要真的去改那一段里的每一个数：

• 这个节点自己的和，一句话就算得出来：sm[o] += x * 段长；
• 至于它底下那些节点，先欠着 —— 在 lz[o] 上记一笔「我欠你们每人一个 x」。

★ lz[o] 的含义：「o 这个节点自己的 sm 已经算进去了，但 o 的两个儿子还不知道这件事。」

⚠ 不是「这一段要加 lz」，也不是「这一段还没加」—— 差一个字，代码就写不对。 （sm[o] 到底算没算 lz[o]？这个问题只有一个答案，而第 11 步那七个 bug 里有三个就死在它上面。）

于是一次区间加只在边界上留下 O(log n) 个「全覆盖」的节点，每个记一笔账就走人。

只有一种时候：当你要往下走、要读儿子的值的时候。 儿子的 sm 是「还没加过 lz[o]」的旧值，直接读就是错的。

把递归到一个节点时的三种情况摆开，答案就是一句话：

⇒ 「懒」到不能再懒为止 —— 一直欠着，直到有人要看儿子。

⚠ 三条推论，每一条都对应第 11 步的一个真 bug：

• 修改和查询两边都要下推（少写一处就是一个 bug —— 而且这两处坏的东西还不一样）；
• 下推完 lz[o] 必须清零（账还了要销账，否则下次路过再还一遍）；
• lz[o] += x，不是 = x（欠了两笔账要叠起来）。

★★ 但请记住「必须下推」的理由，而不是这句话本身：理由是「你要去读儿子的值」。 第 8 步会给出一份一次都不下推的正解 —— 理由消失了，要求也就消失了。

必须下推的理由只有一条：你要读儿子的 sm，而它还不知道你欠它的那笔账。 那么换个办法：账一直挂在打标记的那个节点上（永久化），谁从上面走过去，谁顺手把路过的账补进答案。

• sm[o] = 这一段的真实和，但不含它所有祖先的 tg（自己的 tg 已经算进去了）；
• 区间加：沿途每个节点 sm[o] += x × (交集长度)，走到全覆盖的节点就 tg[o] += x，停；
• 区间查：一路往下带着 add = 沿途所有祖先 tg 之和，到全覆盖的节点返回 sm[o] + add × 段长。

⚠ 它有代价，必须写明：只对「可交换、可叠加」的标记成立（区间加正是）。 碰到区间赋值那种「后来的把先前的盖掉」的标记，顺序一乱就错了 —— 那种情况老老实实下推。

★ 而它在第 5 步那张碰格表里每一档都比懒标记便宜（683 020 / 746 090 / 404 438 对 1 014 442 / 1 321 294 / 876 724）—— 因为它根本没有 pushdown 那两下， 末行也不用一路推账。

★★ 所以这一章要立的规矩是：「必须下推」不是定律，是一个具体的理由。 这和第 32 章那条（「不成立的是那句『取出来就定死』」，而不是「那份代码会错」）是同一种要求： 把结论钉在理由上，别钉在句子上。

这是第 37 章立的规矩（写在 gen.cpp 开头），第 38 章验过一次。这一章的清单天然分成两半：

★★ 上面三个只要「单个操作长什么样」对；下面四个要的是「这个操作和上一个操作之间是什么关系」。 ⚠ 我动笔前据此写下的预判是「这一章要拧一类新旋钮：操作之间的相关性」—— 第 12 步会告诉你这个预判是错的，而且错得能说清。

★★ 这张表里最该记住的是最后那一列：

七个 bug 里只有两个的末行是错的，另外五个末行一个字都不错。 而错的那两个（不销账 / 账被覆盖），毛病正好都出在账本身上； 另外五个坏的是和算得对不对，叶子上的值一点没歪。

⚠ wrongLen 尤其要单独说：它的末行永远正确 —— 叶子的段长是 1，乘不乘一个样。 所以「最后打印一遍数组看看对不对」这种自查方式，对它完全无效。

gen.cpp 带了十二个档位（./gen 种子 档位），种子固定 1..300。 顺序照第 11 步那张清单：Len / Mid / Up / PushQ / PushU / Keep / Apply。

① 真正的功臣只有两个，而且都不新鲜。 序列拉长把最弱的那一支从 51 抬到 237，n 放大抬到 88，合起来就是最终档的 292。

★ 第 36 章的结论（打假「写错的实现」靠操作序列够长）在这一章又一次原样成立 —— 因为这一章四个最难的 bug 要的都是「先埋下、后读出」。

② ⚠ 值域那一档，七列一个数字都没变。 和档位 0 逐位相同。原因也说得清：这道题的 bug 没有一个和数值有关 （这一章连溢出版本都没有 —— 那是第 38 章的主题）。

★ 第 33 章那条「加了个好东西不等于数据变好了」，这一章占第一次。撤回。

③ ⚠⚠ n 是不是 2 的幂，在这一章几乎没有影响（57 vs 59）。 而它在第 38 章是决定性的旋钮（wrongEnd 300 vs 177、wrongVar 170 vs 279）。 差别在于bug 吃的是什么：

树状数组的 bug 直接吃 lowbit(下标)，所以下标的二进制形状就是生死； 线段树的 bug 吃的是「查询区间和节点区间的相对位置」—— 而树切得整不整齐，并不改变「一个随机区间会不会跨过某个 mid」这件事的概率。 ★ 第 38 章那条「第五类旋钮」是真的，但它属于树状数组，不属于「所有数据结构」。

④ ⚠ 「修改占七成」也是负分（最弱支 51 → 56 看着涨了，可 Len / Mid / Up / PushQ 四列一起掉）。 道理很直白：改多了就没人来读了 —— 这些 bug 全都要「有人来读」才现形。 第 31 章那条「某一支占得太多也是坑」的又一次。

前面十三章一路在总结「怎么把数据调狠」。这一章第一次遇到的是另一种局面：

★★ 我提前想清楚了 bug 靠什么现形（那一步是对的、也是必要的）， 可「靠什么现形」和「该拧哪个旋钮」之间，还隔着一个必须实测的问题： 这个性质，随机数据是不是本来就免费送？

• 第 38 章那次（下标的二进制形状）：随机数据不送 —— n = 2^k 在 [6,12] 里只占 1/7， 而它是那个 bug 的生死线 ⇒ 必须专门造；
• 这一章（区间的包含关系）：随机数据白送 12.5% ⇒ 专门造纯属白干，还有副作用。

⚠ 两次的前半段完全一样（都把 bug 靠什么现形写清楚了）， 分岔点在后半段 —— 而那一半只能靠量。

single.cpp 的输入输出和 code/38-fenwick/ 那几份一字不差， 所以能直接拿第 38 章的生成器跨章节对拍 300 轮（那个生成器一个字都没改）。

点「运行 ▶」看结果

并排量一次（./genBig 200000 200000 1，也就是第 38 章那份大数据；跑 20 次取总耗时）：

cd code/38-fenwick && g++ -O2 -o genBig genBig.cpp && g++ -O2 -o fen fast.cpp && g++ -O2 -o count count.cpp
g++ -O2 -o seg ../39-segment-tree/single.cpp
./genBig 200000 200000 1 > big.txt
time (for i in $(seq 1 20); do ./fen < big.txt > /dev/null; done)

★ 所以那句口口相传的「树状数组常数小」，在这道题上是量得出来的：约 6~7 倍。 ⚠ 但要说清它为什么小：树状数组一次 sum(r) 只走 popcount(r) ≈ log₂n / 2 格连续数组， 线段树一次查询要递归进 O(4 log n) 个节点、每一步都是一次跳转。 不是「线段树写得差」，是它多做了「能做更多事」所必须的那些工作。

点「运行 ▶」看结果

改的是这两处（其余一个字都没动）：

★ 什么时候打标记、什么时候必须下推、下推完要销账 —— 一句都没变。 这就是「线段树能干的事多」的具体含义：只要「两个儿子的答案能合并成父亲的答案」，框架就照搬。

⚠ 而树状数组做不到：它靠「sum(r) − sum(l−1)」拿区间和， 而最大值没有减法 —— 第 38 章那句「可以修改的前缀和」，前缀这两个字是有代价的。

check:viz 里 300 轮对拍：maxBrute ↔ maxSeg， ★ 而且生成器一个字都没改 —— 同一串操作、同一批数据，只换了合并方式。