课前零食：会变化的区间和

静态前缀和很舒服：问一段和只要相减。可一旦数组会改，旧前缀和就像一串被推倒的多米诺骨牌。今天先发明两种“只修少量摘要”的办法：Fenwick Tree 和 Segment Tree。

本节目标

学完后，你能：

从静态前缀和的优点和单点修改的代价，推出需要分层摘要；
把 lowbit(i) 理解成 Fenwick 节点负责的区间长度，而不只是一段位运算；
理解线段树节点为何存一个区间的合并结果、查询为何只取少数节点；
知道 Fenwick 与线段树各自适合什么聚合操作，为正式课的高级变式打地基。

前置知识与课前自测

前置：数组、二进制最低位、区间和、递归的基本概念。

前缀和 pre[r]-pre[l-1] 为什么能得到区间 $[l,r]$ 的和？
修改 a[2] 后，哪些 pre[i] 必须更新？
i & -i 在二进制中会留下 i 的哪一部分？

答案

1. 前 $l-1$ 个元素在两份和中抵消。2. 所有 $i\ge2$ 的前缀和，最坏 $O(n)$ 个。3. 最低位的 1 及其对应数值，例如 `12=1100₂` 的 `lowbit` 是 4。

互动规则：每个格子都必须说清“我替谁记账”

准备数组 a=[3,1,4,1,5,9]，下标从 1 开始。每次结构中出现一个新格子，都在它下面写清楚：它汇总原数组的哪一段？不要只记录 tree[i] 的数值。纸上账本分成：原数组、摘要数组/节点、一次查询拿了哪些摘要、一次修改通知了哪些摘要。

本节的互动目标是从“完整前缀和”亲手发明“局部摘要”。若某个节点的负责区间说不出来，它还不是你真正会用的数据结构。

从零搭框架：让前缀和先享受、再付出代价

第 0 步：先把静态前缀和手算出来

对 a=[3,1,4,1,5,9] 写 pre[0]=0，再逐项填 pre[i]=pre[i-1]+a[i]。用它回答 sum(2,5)。

停顿 0：为什么只需 pre[5]-pre[1]？请在两个和里圈出被抵消的元素，而不是只引用公式。

展开：静态摘要的威力

`pre=[0,3,4,8,9,14,23]`，`sum(2,5)=14-3=11`。前 1 项在两份前缀中都出现而抵消；静态时一次预处理换来 $O(1)$ 查询。

第 1 步：亲手修改一次，数清谁被连累

把 a[3] 从 4 改成 10。不要重算前缀和前先猜：pre[1],pre[2],pre[3] 到 pre[6] 中，哪些应改变？在每个应改变项后写 +6。

停顿 1：若有十万次“改单点、问区间”，完整前缀和的哪一部分会反复重做？我们真正想保留的是什么，又不想每次重算什么？

展开：局部摘要的需求

只有 `pre[3]..pre[6]` 都加 6，单次修改最坏碰 $O(n)$ 项。我们想继续保留“一个摘要代表一段连续元素”的好处，但让一个元素只影响少量层级摘要，而不是所有后缀。

第 2 步：先人工分块，再发现二进制块

把下标 1..8 先粗暴分成 [1,4]、[5,8] 两块。问 prefix(6) 时，你会拿整块 [1,4]，再处理 [5,6]。请继续把 [5,6] 看成一个摘要块。

现在写下 1..8 的二进制和 lowbit(i)：

i	二进制	`lowbit(i)`	若 `tree[i]` 负责尾块，它负责哪段
1
2
4
6
8

停顿 2：从 6 不断减 lowbit 会走到哪些下标？这些块为什么刚好不重不漏地覆盖 [1,6]？

展开：Fenwick 是一套可拼接的尾块目录

6 的 `lowbit` 为 2，先拿 `[5,6]`；6-2=4，再拿 `[1,4]`；4-4=0 停止。二进制每次去掉最低位 1，得到的尾块恰好从右向左拼满前缀。`tree[6]` 不是第 6 个元素，而是 `[5,6]` 的和。

第 3 步：更新为什么反向加 lowbit

仍改位置 3，先问：哪些尾块包含 3？从下标 3 开始不断加 lowbit，把走到的下标和对应区间写出来。

停顿 3：为什么 3、4、8 都需要更新，而 6 不需要？请用“负责区间是否包含 3”解释，别只背跳法。

展开：查询和更新是一对反向目录操作

3 负责 `[3,3]`，4 负责 `[1,4]`，8 负责 `[1,8]`，它们都包含位置 3；6 负责 `[5,6]`，不含 3。减 lowbit 是把前缀拆成块，加 lowbit 是通知所有包住该点的块。

第 4 步：当“相减”不成立时，换一棵摘要树

若查询的是区间最小值，写两个前缀最小值：min(1..r) 与 min(1..l-1)。请尝试从它们恢复 min(l..r)，再构造一个反例说明失败。

然后把 [1,8] 二分为 [1,4],[5,8]，继续二分。每个节点记录自己区间的最小值或和。请回答：查询 [2,7] 时，哪些完全包含的节点可以直接交答案，哪些边界节点还需继续拆？

展开：线段树只要求摘要可合并

最小值不能像和一样相减；例如两个前缀最小值都为 1，无法知道区间内部最小值。线段树让每个节点保存一段摘要，查询只拿完全被覆盖的节点，再用 `combine` 合并。它不要求可逆，只要求合并规则与区间划分一致。

问题动机：一边快查询，一边快修改，不能全靠一张表

原数组直接求区间和，每次查询 $O(n)$、修改 $O(1)$；完整前缀和反过来，查询 $O(1)$、修改 $O(n)$。如果有十万次查询和修改，任何一边全重算都会累趴。解决方案是保留许多局部摘要，一次操作只触碰对数层。

步步式引导

1. Fenwick：按二进制块拼前缀

从 1 开始编号。tree[i] 不保存单点，而保存区间：

$$ [i-\operatorname{lowbit}(i)+1, i]. $$

求前缀和时，从 i 开始反复减去 lowbit(i)，每次吃掉一个不重叠的尾部块；更新位置 i 时，反复加 lowbit(i)，恰好通知所有包含它的摘要块。

prefix_sum(i):
    result = 0
    while i > 0:
        result += tree[i]
        i -= lowbit(i)
    return result

add(i, delta):
    while i <= n:
        tree[i] += delta
        i += lowbit(i)

lowbit 不是随机跳跃：二进制最低位 1 指出当前位置结尾、大小合适的块。每次跳会去掉一个 1，最多 $O(\log n)$ 次。

2. 线段树：让每个区间都有一个小管家

若操作不只是可相减的和，例如区间最小值，prefix_min(r)-prefix_min(l-1) 没有意义。线段树把 $[1,n]$ 反复二分，每个节点保存其区间的合并结果；查询 $[l,r]$ 时，完全落在目标内的节点直接拿摘要，相交一部分才继续向下问。

query(node, left, right, ql, qr):
    if [left, right] is fully inside [ql, qr]:
        return summary[node]
    split at mid
    combine answers from overlapping children

point_set(node, left, right, index, value):
    if left == right: summary[node] = value; return
    recurse into the child containing index
    summary[node] = combine(left_child, right_child)

纸上模拟：让同一条查询走两条不同的摘要路线

初始数组仍为 [3,1,4,1,5,9]。先完成 sum(2,5)，再执行 set(3,10)，最后再问一次 sum(2,5)。每次都填：

操作	Fenwick 拿/改的块	线段树拿/重算的区间节点	结果
`sum(2,5)`
`set(3,10)`
`sum(2,5)`

展开：两种结构省掉的是同一种重复劳动

第一次答案为 11，更新后为 17。Fenwick 用 `prefix(5)-prefix(1)`，其中会拼 `[5,5]`、`[1,4]` 等尾块；线段树取若干完全覆盖的区间节点并合并。它们的形状不同，但都避免了逐元素重算整段，操作只触碰对数层摘要。

每层至多拆开目标区间两边，树高为 $O(\log n)$，所以单点改与区间问都是 $O(\log n)$。

核心知识：选择结构前先问“摘要能不能合并、能不能反推”

Fenwick 最擅长可用前缀差还原区间的操作，例如和、计数、XOR；取最小值通常不能从两个前缀最小值相减出来。线段树只要求 combine 满足结合性，能维护和、最值、最大子段和等更丰富摘要，但常数和实现复杂度较高。

两者都不是“自动处理所有区间操作”的万能盒：若更新影响整段、查询也问整段，普通节点摘要不够，需要 Lazy 标记；若值域很大或版本很多，正式课会继续引入动态开点、可持久化与合并分裂。

实现指南

Fenwick 通常 1-based；i=0 时 lowbit(0)=0 会原地踏步，千万别让循环从 0 开始。
查询闭区间和统一写成 prefix(r)-prefix(l-1)，不要一会儿闭区间一会儿半开区间。
线段树的 combine、空区间单位元、叶子含义必须一致；求最小值的单位元不是 0。
先写小数组并打印每个节点代表的区间，再追求“精简模板”；短代码不等于短思考。

互动小实验室

运行会变化的区间和.py。它同时维护一份 Fenwick 与一棵线段树；可以输入：

sum l r：看 Fenwick 分解出的前缀块和线段树选中的节点；
set i x：看一次修改向上的 Fenwick 摘要和线段树祖先；
show：列出每个 tree[i] 真正负责的区间。

直接回车会退出，适合先读默认摘要；推荐先输入 sum 2 5，再 set 3 10，再问一次同一区间。

扩展与联系

Fenwick 的“按二进制块前缀分解”常用于离线计数和逆序关系；线段树的“摘要 + 合并”则是区间 DP、扫描线、可持久化结构的母语。两者共享的识别信号是：数组会变化，但每次只问一个可合并的区间性质。

总结与自检

Fenwick 的 tree[i] 为什么不是 a[i]？
为什么区间最小值不适合直接做“两个前缀最小值相减”？
线段树为何只递归到与查询区间相交的部分？

自检答案

它保存一个二进制尾块摘要；最小值没有可逆减法；完全不相交的节点对答案没有贡献，完全包含的节点已有足够摘要。

一周预热安排

第 1 天：写出 1 到 8 的 lowbit 和各自负责区间。
第 2 天：用 Fenwick 块拼出 prefix_sum(13)。
第 3 天：给 8 个数画一棵区间二叉树。
第 4 天：运行互动程序，比较同一查询的两种分解。
第 5 天：进入Fenwick 离线计数正式课。

00-课前零食-会变化的区间和.md 11 KB History Raw