一起动脑筋 · 先看一个小故事
女孩反复问连续几天读了多少页。机器人先记“到这天为止一共多少”，以后就能用相减回答。
把过程摊开来看
- 原数据2、3、4
- 前缀和0、2、5、9
- 问第 2 到 3 天9 减 2
- 答案7 页
前缀和保存从开头到某位置的累计总量。
这里用前缀和数组 P，P[0] = 0；第 2 到 3 项的和是 P[3] − P[1]，去掉第一项之前的部分。
01如果总是问区间和怎么办？
数组：
2 5 3 7 4如果只问一次“第 2 到第 4 个数的和”，直接相加没问题。
但如果要问成千上万次，每次重新加就会重复做很多工作。
02什么是前缀和？
先把从开头到当前位置的累计和算好。
| 前 i 个元素 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| prefix[i] | 0 | 2 | 7 | 10 | 17 | 21 |
03为什么多放一个 prefix[0]=0？
这是非常常见的设计：
prefix[0] = 0;
prefix[i] = prefix[i - 1] + a[i];如果原数据使用 1-based 下标，prefix[i] 就表示前 i 个元素之和。
04区间和为什么只要相减？
要得到从 l 到 r 的和：
sum(l,r) = prefix[r] - prefix[l-1]
因为 prefix[r] 包含前 r 个数，减掉前 l-1 个数，正好留下 l 到 r。
05为什么查询会变快？
每次直接累加
区间很长时要访问很多元素。
前缀和
每次查询只做固定数量的数组访问和减法。
构建前缀和需要 O(n)，之后每次普通区间和查询可以 O(1)。
06前缀和会溢出吗？
会。即使每个元素能放进 int，累计和也可能超过 int。
std::vector<long long> prefix(n + 1);信奥中应先估算最大总和，再选择类型。
07数组更新后怎么办？
普通前缀和适合“数据基本不变、查询很多次”的情况。
如果原数组频繁修改，后面的很多前缀值都可能受影响，这时会学习树状数组、线段树等更合适的结构。
你已经知道了什么
- 前缀和保存从开头到当前位置的累计结果。
- 常见定义让
prefix[0]=0。 - 区间 [l,r] 的和可由两个前缀值相减得到。
- 预处理 O(n)，普通区间和查询 O(1)。
- 累计和要注意整数溢出。
下一篇：贪心：每一步先做最好的选择
轮到你来试一试
第 1 到 2 天的总页数为什么是 5 − 0？
想好了吗？点开看解释
P[2] 包含前两天，P[0] 表示尚未包含任何天，减去 0 得 5。这个额外的 0 让边界更统一。