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

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

## 本节目标

学完后，你能：

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

## 前置知识与课前自测

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

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

<details><summary>答案</summary>

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

</details>

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

准备数组 `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]`？请在两个和里圈出被抵消的元素，而不是只引用公式。

<details><summary>展开：静态摘要的威力</summary>

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

</details>

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

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

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

<details><summary>展开：局部摘要的需求</summary>

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

</details>

### 第 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]`？

<details><summary>展开：Fenwick 是一套可拼接的尾块目录</summary>

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

</details>

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

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

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

<details><summary>展开：查询和更新是一对反向目录操作</summary>

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

</details>

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

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

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

<details><summary>展开：线段树只要求摘要可合并</summary>

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

</details>

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

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

![Fenwick 节点保存的尾部区间](../插图/08-高级线段树与树状数组/00-区间-01-Fenwick覆盖.svg)

## 步步式引导

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

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

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

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

```text
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]$ 时，完全落在目标内的节点直接拿摘要，相交一部分才继续向下问。

![线段树把区间递归分块](../插图/08-高级线段树与树状数组/00-区间-02-线段树分块.svg)

```text
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)` |  |  |  |

<details><summary>展开：两种结构省掉的是同一种重复劳动</summary>

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

</details>

每层至多拆开目标区间两边，树高为 $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](../../互动程序/08-高级线段树与树状数组/00-会变化的区间和.py)。它同时维护一份 Fenwick 与一棵线段树；可以输入：

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

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

## 扩展与联系

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

## 总结与自检

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

<details><summary>自检答案</summary>

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

</details>

## 一周预热安排

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