前缀和
前缀和把反复的区间求和变成常数时间的操作。对数组扫一遍，写下累计和 prefix[k] = nums[0] + … + nums[k − 1]；之后任意连续区间 nums[l..r] 的和都是 prefix[r + 1] − prefix[l]。只读两个值、做一次减法，不管区间是一格还是整个数组。
想想自驾时的里程表。每到一个城镇就记下读数，以后想知道某一段有多长，不必再开一遍：从第 2 个镇到第 6 个镇的距离，就是两个读数相减。前缀和对数组做的是同一件事：把工作从提问时挪到事先的一次记账里。
前缀和的工作原理
在每两个相邻格子之间立一条分隔线，第一个格子前和最后一个格子后也各立一条。长度为 n 的数组有 n + 1 条分隔线，编号 0 到 n。于是 prefix[k] 就是分隔线 k 左边所有值的和。分隔线 0 左边什么都没有，所以 prefix[0] = 0；prefix[n] 是整个数组的和。
构建只需一个循环。每一项等于上一项加上刚越过的那个格子：prefix[k] = prefix[k − 1] + nums[k − 1]。共 n 次加法，只做一次。
查询 nums[l..r]（两端都包含）需要夹住这个区间的两条分隔线：分隔线 l 在 nums[l] 之前，分隔线 r + 1 在 nums[r] 之后。分隔线 r + 1 左边的全部，减去分隔线 l 左边的全部，剩下的正好是这个区间；共同的部分 nums[0..l − 1] 被消掉了。查询只有一行，没有循环，代价与 r − l 无关。
开头那个 0 不是摆设。没有 prefix[0] = 0，从 l = 0 开始的查询就没有可减的值，得单独写一个分支。有了它，sum(0..r) = prefix[r + 1] − prefix[0] 直接套用同一个公式。
这个方法不在乎正负号。负数只会让累计和往下走一点，减法照样能把共同部分精确消掉。最短长度滑动窗口课中的贪心收缩依赖非负值。固定长度的滑动窗口没有这个限制，前缀和也能处理有正有负的数组。
代价出现在数组被修改的时候。所有 k > i 的 prefix[k] 都包含 nums[i]，所以改动一个值，后面 n − i 个值全部失效。每一个都要加上同一个 delta = 新值 − 旧值，下一次查询才能信任这一行。
前缀和逐步演示
默认输入是 nums = [3, 1, 4, -2, 5, 9, 2, 6]，有四个查询：sum(2..5)、sum(0..7)、sum(4..4) 和 sum(1..6)。
先看问题。 sum(2..5) 是多少？逐个读取 4、−2、5 和 9，累计结果是
4 → 2 → 7 → 16，共读四次。接着再问 sum(0..7)，直接求和又要重新扫描。
前缀表把这些工作存下来，供后面的查询复用。开场扫描演示直接求和，下面的对照则比较
同一个数组上的四个查询。
构建。 从 prefix[0] = 0 开始，每步加一个格子：
prefix[1] = 0 + 3 = 3prefix[2] = 3 + 1 = 4prefix[3] = 4 + 4 = 8prefix[4] = 8 + (−2) = 6。累计和下降了，但什么也没坏。prefix[5] = 6 + 5 = 11- 第 6–8 步照此继续：
20、22、28。
建好的一行是 prefix = [0, 3, 4, 8, 6, 11, 20, 22, 28]，用了 8 次加法。
查询。 每个查询读两个值：
sum(2..5) = prefix[6] − prefix[2] = 20 − 4 = 16。直接求和要读 4 个格子。sum(0..7) = prefix[8] − prefix[0] = 28 − 0 = 28。整个数组，仍然只读 2 个；开头的 0 在这里派上用场。sum(4..4) = prefix[5] − prefix[4] = 11 − 6 = 5。单个格子，仍然读 2 个。sum(1..6) = prefix[7] − prefix[1] = 22 − 3 = 19。六个格子，读 2 个。
直接对每个区间求和共要读 4 + 8 + 1 + 6 = 19 个格子。前缀和的查询读 8 个值，外加构建时一次性花掉的 8 次加法。
画布上的 prefix[k] 位于分隔线 k 下方。前两次加法同时强调原来的累计和与新加入的值。
第一个查询先读右边的累计和，再读左边的累计和，消掉两者共有的格子，最后停留在答案上。
条长表示覆盖的位置，不表示和值大小：很长的一段也可能合计为 0。后面的查询加快重复同一条规则。
底部的 prefix reads 始终为 2，direct reads 则依次为 4、8、1、6。
加载 单点更新 场景可以看到另一面。在 sum(0..5) = 20 之后，nums[1] 从 1 改成 7（Δ = +6）。prefix[2..8] 全部失效，修复循环把这七个值逐一重写，同一个查询再问一次，才得到 26。
时间与空间复杂度
| 操作 | 时间 |
|---|---|
| 构建 | O(n) |
| 区间求和查询 | O(1) |
| 单点更新（动画中的做法） | O(n − i)，最坏 O(n) |
| 直接区间求和（对照） | O(r − l + 1) |
空间为 O(n)，存 n + 1 个前缀值。数组很少变化、又反复查询较长区间时，复用累计和可能摊平构建开销。
单格查询直接读取一次就够了，前缀和的两次读取未必更省。在不变的数组上做 q 次查询，
总时间复杂度是 O(n + q)，而直接求和最坏是 O(n · q)。
更新频繁时，普通的前缀数组就不合适了。树状数组（Fenwick 树）或线段树能在 O(log n) 内同时完成区间求和与单点更新。本课动画用的是普通数组，好让更新的代价看得见，而不是被藏起来。
边界情况
- 从下标 0 开始的区间。
sum(0..r) = prefix[r + 1] − prefix[0]，而prefix[0] = 0。不需要特殊分支。 - 单个格子的区间。
sum(i..i) = prefix[i + 1] − prefix[i] = nums[i]。仍然读两个值。 - 整个数组。
sum(0..n − 1) = prefix[n]。最后一项就是总和。 - 负数。 累计和可升可降，答案始终精确。默认运行中它从 8 降到 6。
- 相等的前缀值。 若
prefix[a] = prefix[b]，则区间nums[a..b − 1]的和为 0。相等的累计和 场景在一个数组里展示了三个这样的区间，这正是"统计和为 k 的子数组"的起点。 - 更新第一个或最后一个下标。 改
nums[0]要重写后面全部n个值；改nums[n − 1]只需重写prefix[n]。
常见错误
- 对包含两端的区间用
prefix[r] − prefix[l]。 这会漏掉nums[r]。nums[l..r]的右分隔线是r + 1，这也是前缀数组有n + 1项的原因。 - 存到
nums[k]为止的和、不留开头的 0。 数组少一项，每个l = 0的查询都得加一个if，差一错误往往就聚集在这个分支附近。 - 在查询里重新构建。 每次查询都调用
build(nums)，或在循环里求nums[l:r + 1]的和，又回到了每次 O(n)。构建一次，反复使用。 - 忘了前缀数组只是一张快照。
nums[i]改变后，所有k > i的prefix[k]都过时了。要么用prefix[k] += delta全部修复，要么换成树状数组。 - 长输入忽略溢出。 在定长整数的语言里，即使每个值都放得下，累计和也可能超出类型范围。前缀数组要用更宽的类型。