01先读懂这个概念
重复查询重复了哪些工作
对 a=[2,−1,3,4]，如果每次询问一个区间都重新相加，q 次查询最坏 O(qn)。例如 [0,3) 和 [1,4) 都重复计算了中间的 −1、3。既然输入不变，可以提前记录每个前缀的和。
约定 P[i] 是前 i 项的总和，也就是 a[0:i]。因此 P[0]=0，P[1]=2，P[2]=1，P[3]=4，P[4]=8。P 的长度是 n+1；它的下标描述元素之间的边界，不是某一个元素的值。
公式来自减掉左边那一段
P[r] 包含 a[0] 到 a[r−1]，P[l] 包含 a[0] 到 a[l−1]。相减后，前 l 项逐项抵消，剩下 a[l] 到 a[r−1]。所以半开区间 [l,r) 的和是 P[r]−P[l]，元素个数是 r−l。
查询 [1,4) 时，8−2=6，直接相加 −1+3+4 也等于 6。负数不会影响抵消；不像某些按区间和移动窗口的算法，前缀和本身不要求和随着边界移动而单调。
02从具体数据开始手算
拿一个小输入，逐步手算
为 [2,−1,3,4] 构造前缀和，再查询 [1,4)。
| 处理元素 | 计算 | 已得到的 P |
|---|---|---|
| 还没处理 | 空前缀为 0 | [0] |
| 2 | 0+2=2 | [0,2] |
| −1 | 2−1=1 | [0,2,1] |
| 3 | 1+3=4 | [0,2,1,4] |
| 4 | 4+4=8 | [0,2,1,4,8] |
| 查询 [1,4) | P[4]−P[1]=8−2 | 答案 6 |
P[0]=0 让从开头开始的查询也使用同一条公式。空区间 [l,l) 的答案自然是 0。
03把正确性的理由说清楚
构造与查询各自正确
- P[0]=0 正确表示空前缀。
- 假设 P[i] 已是前 i 项的和，加上 a[i] 就得到前 i+1 项的和，所以逐项构造正确。
- P[r]−P[l] 消去相同的前 l 项，只留下要求的区间；先固定半开约定，就无需在公式中猜是否加 1。
04把刚才的思路写成代码
基础课用 Python 表达，先对照变量含义与执行顺序。后续算法课提供 Python、C++ 与 JavaScript 三种实现。
def build_prefix(a):
prefix = [0]
for value in a:
prefix.append(prefix[-1] + value)
return prefix
def range_sum(prefix, left, right):
return prefix[right] - prefix[left]代码里的每个关键决定
prefix = [0]- 为没有任何元素的前缀保留一个边界值。不是因为数组必须包含 0。
prefix.append(prefix[-1] + value)- 最新前缀加上当前元素，就是下一项前缀。此处 −1 是 Python 取最后一项的下标语法。
prefix[right] - prefix[left]- 调用前保证 0≤left≤right≤n。如果题目给闭区间 [l,r]，要查询到右边界 r+1，即 P[r+1]−P[l]。
05这些操作要付出多少代价
把工作量具体数出来
预处理 n 次累加，O(n) 时间；q 次合法查询各做一次减法，总时间 O(n+q)。
保存 n+1 个累计值，辅助空间 O(n)。不是每次查询都重新构造 P；如果那样做，就失去了预处理收益。
单点修改 a[k] 会影响所有 P[k+1] 到 P[n]，直接维护需 O(n)。频繁修改又频繁查询时，后续可学树状数组或线段树。
06用一个反例检查理解
少加一个右边界就少算一项
想求闭区间 a[1..3] 的和，却写 P[3]−P[1]=4−2=2，只算到下标 2，漏了 a[3]=4。
怎样修正：先把题意转成半开区间 [1,4)，再计算 P[4]−P[1]=6。每次写公式前把包含哪些下标写清楚。
07自己推一次，再做自测
用两种办法核对
a=[3,−2,5,1]。写出 P，再求半开区间 [1,3) 和闭区间 [1,3] 的和。
需要一点提示
两道查询的右边界不同。
查看完整推导与答案
- P=[0,3,1,6,7]。
- [1,3) 包含 −2、5，答案 P[3]−P[1]=6−3=3。
- [1,3] 还包含最后的 1，答案 P[4]−P[1]=7−3=4。