前缀和数组是什么？为什么能把区间求和从 O(n) 优化到 O(1)？

简化版

前缀和数组把“从开头到当前位置的累计和”提前存起来。查询区间 [l, r] 的和时，用 prefix[r + 1] - prefix[l] 就能 O(1) 得到结果。

详细版

前缀和适合数组不频繁修改、但区间求和很多的场景。

原数组 nums 长度为 n，常建长度 n + 1 的 prefix。
prefix[0] = 0，prefix[i + 1] = prefix[i] + nums[i]。
区间 [l, r] 的和是 prefix[r + 1] - prefix[l]。
多次查询时，预处理 O(n)，每次查询 O(1)。
如果数组频繁修改，普通前缀和维护成本高，可能要用树状数组或线段树。

完整版教学

一、为什么区间求和会被重复计算拖慢

如果每次查询区间和都从 l 遍历到 r，一次查询是 O(k)，多次查询会重复扫描大量元素。比如长度 10 万的数组，有 10 万次区间查询，每次平均扫 1000 个元素，总访问量就是 1 亿级。前缀和的思想是把“重复从头累加”的工作提前做一次，后续查询只做一次减法。它本质上是用空间换时间，把多次重复计算变成一次预处理。

nums:   [2, 4, 1, 7, 3]
prefix: [0, 2, 6, 7, 14, 17]

记忆钩子：前缀和不是让加法消失，而是把很多次区间内加法提前合并成一次“前缀差”。

二、为什么常用 `n + 1` 长度

很多初学者直接让 prefix[i] 表示 nums[0..i] 的和，这当然也能做，但查询时边界会多一个特判。更常见的写法是让 prefix[0] = 0，prefix[i] 表示前 i 个元素的和，也就是 nums[0..i-1]。这样区间 [l, r] 就统一写成 prefix[r + 1] - prefix[l]，哪怕 l = 0 也不需要特判。这个设计是数组题里很典型的“哨兵位置”思想。

const prefix = new Array(nums.length + 1).fill(0);
for (let i = 0; i < nums.length; i++) {
  prefix[i + 1] = prefix[i] + nums[i];
}

三、公式为什么成立

prefix[r + 1] 表示 nums[0] 到 nums[r] 的总和，prefix[l] 表示 nums[0] 到 nums[l - 1] 的总和。两者相减，前面重叠的 nums[0..l-1] 被消掉，剩下的正好是 nums[l..r]。这不是背公式，而是“更大的前缀减掉不需要的前缀”。理解这个消除关系后，二维前缀和、子数组和、差分数组都会更容易学。

prefix[r+1] = nums[0] + ... + nums[l-1] + nums[l] + ... + nums[r]
prefix[l]   = nums[0] + ... + nums[l-1]
相减后      = nums[l] + ... + nums[r]

四、带数字算一遍

假设 nums = [2, 4, 1, 7, 3]，要查 [1, 3]，也就是 4 + 1 + 7。前缀和是 [0, 2, 6, 7, 14, 17]，所以结果是 prefix[4] - prefix[1] = 14 - 2 = 12。如果查询 [0, 2]，结果是 prefix[3] - prefix[0] = 7 - 0 = 7，不需要单独处理从 0 开始的区间。

查询区间	公式	结果
`[1, 3]`	`prefix[4] - prefix[1]`	`12`
`[0, 2]`	`prefix[3] - prefix[0]`	`7`
`[3, 4]`	`prefix[5] - prefix[3]`	`10`

五、什么时候前缀和不合适

前缀和适合“数组静态、查询很多”的场景。如果数组经常更新，改动一个位置会影响后面所有前缀值，最坏要 O(n) 更新。比如 nums[2] 加 5，那么 prefix[3] 之后都要跟着变化。此时如果同时有大量更新和查询，树状数组或线段树更合适，因为它们能在 O(log n) 里完成单点修改和区间查询。

静态数组 + 多次区间和：前缀和
频繁单点修改 + 区间和：树状数组/线段树
频繁区间修改 + 单点查：差分数组

六、二维前缀和是同一个思想的扩展

二维数组里，如果要频繁求矩形区域和，也可以预处理二维前缀和。核心仍然是“大区域减掉不要的区域”，只不过要额外加回被减了两次的左上角区域。理解一维前缀和的相减消除后，二维公式就不神秘了。很多图像处理、地图统计、矩阵子区域求和都依赖这个思想。

sum(x1,y1,x2,y2)
= S[x2+1][y2+1] - S[x1][y2+1] - S[x2+1][y1] + S[x1][y1]

七、常见误区与追问

误区：prefix 长度必须等于原数组。 长度 n + 1 更常用，可以统一处理从 0 开始的区间。
误区：前缀和查询是 O(0)。 它仍然做常数次数组访问和减法，复杂度是 O(1)。
误区：数组修改后前缀和不用变。 普通前缀和依赖原数组值，修改会影响后续前缀。
追问：为什么公式是 r + 1？ 因为 prefix[i] 表示前 i 个元素的和，r 位置包含在前 r + 1 个元素里。
追问：如果有负数还能用吗？ 能，前缀和只依赖加减法，不要求元素非负。

八、加强记忆

前缀和可以记成“前面累计账本”。每个位置记录从开头到这里之前的总账，查区间时用右边账本减左边账本，中间那段自然露出来。面试里按“预处理定义 → 查询公式 → 数字例子 → 修改场景不适合”来答，就能同时讲清原理和边界。

简化版

详细版