提前算好"从头到这里的总和"，后面任何一段区间的和都能一步算出来，不用每次重新累加。
假设有一组数据（比如某店铺连续 8 天的销售额），题目会反复问"第 L 天到第 R 天一共卖了多少"——这种"区间求和"的问题如果问一次两次，直接挨个加起来就行；但如果要回答很多次这样的问题，每次都重新累加一遍，会非常浪费——明明很多天都被反复加过很多遍。
前缀和的思路是：提前花一次力气，把"从第一天到第 i 天的总和"都算好、存起来；之后无论问哪一段区间的和，只需要做一次减法，不需要再重新累加。
用 8 天的销售额 {3, 1, 4, 1, 5, 9, 2, 6} 演示。开一个"前缀和数组" prefix，让 prefix[i] 表示原数组前 i 个数的总和（约定 prefix[0] = 0，表示"一个数都没加"）：
| 1 | int arr[] = {3, 1, 4, 1, 5, 9, 2, 6}; |
| 2 | int n = 8; |
| 3 | int prefix[n + 1] = {0}; // prefix[0]=0，表示"前0个数的和" |
| 4 | for (int i = 1; i <= n; i++) |
| 5 | { |
| 6 | prefix[i] = prefix[i - 1] + arr[i - 1]; // 前i个数的和 = 前i-1个数的和 + 第i个数 |
| 7 | } |
prefix 要开 n+1 大小、从下标 1 开始存？把 prefix[0] 留给"空区间，一个数都没加"，prefix[i] 对应原数组第 i 个数（从 1 开始数）为止的总和——这样下标和"第几个数"对得整整齐齐，避免反复处理"减一"这种容易出错的细节，下一节求区间和的时候会感受到这样设计的方便之处。prefix[5] = 14，表示原数组第 1~5 天的销售额总和是 3+1+4+1+5=14；prefix[8] = 31，是全部 8 天的总和。每一格都只比前一格多加了一个新数，构建整个 prefix 数组只需要 O(n) 的时间。想知道原数组第 L 天到第 R 天（包含两端）的总和，不需要再挨个累加——直接用 prefix[R] - prefix[L-1] 就行。可以把 prefix[i] 想象成"汽车开到第 i 公里时的总里程表读数"：要知道从第 L 公里到第 R 公里之间开了多远，只需要用"到达 R 时的读数"减去"到达 L 之前（也就是 L-1）时的读数"——中间重复的部分会在减法里自动抵消掉。
4,1,5,9 正是第 3~6 天的数据，直接相加确实是 19，和前缀和算出来的结果完全一致。蓝色 3,1（第1~2天）是 prefix[2] 已经包含、但查询区间不需要的部分，被减法直接抵消；橙色 2,6（第7~8天）则从来没有被包含进 prefix[6]，自然也不会出现在结果里。| 1 | int RangeSum(int prefix[], int l, int r) // 查询原数组第l到第r个数的和 |
| 2 | { |
| 3 | return prefix[r] - prefix[l - 1]; |
| 4 | } |
l = 1，公式里要用到 prefix[0]——这正是为什么一开始要专门留出 prefix[0] = 0 这个"空区间"。如果没有这一位，l=1 时就要单独写一个特判（"如果从第一个数开始，直接用 prefix[r]，否则用减法"），多留这一位刚好省掉了这个麻烦。假设数组长度 n=1000，一共要回答 1000 次区间和查询：
n 次，1000 次查询总共要做约 n×q=100万 次加法；前缀和只需要 一次性花 O(n) 构建数组，之后每次查询都是 O(1) 的减法，总共约 n+q=2000 次运算——足足快了 500 倍。查询次数越多，前缀和的优势就越明显。| 做法 | 预处理 | 单次查询 | q 次查询总复杂度 |
|---|---|---|---|
| 每次直接累加 | 无 | O(n) | O(n × q) |
| 前缀和 | O(n) | O(1) | O(n + q) |