想象一下，你有一个装满数字的数组，比如 [1, 2, 3, 4, 5]。现在，老师给你出了一个问题：“请快速算出从第 2 个数字到第 4 个数字的和是多少？”
你可能会想：“这还不简单吗？直接把 2 + 3 + 4 加起来就行了，等于 9。” 但如果老师问的是“从第 1 个到第 5 个数字的和”，或者“从第 3 个到第 100 个数字的和”，甚至“有 1000 次这样的问题”，每次都从头算一遍，就会非常麻烦。有没有更聪明的办法呢？
这时候，前缀和数组就能派上用场了！
什么是前缀和数组？¶
前缀和数组（Prefix Sum Array）是一个辅助数组，它的每个元素表示原数组中前若干个元素的和。
比如，原数组是 A = [1, 2, 3, 4, 5]，我们可以构造一个前缀和数组 S，其中：
- S[0] = 0（代表“前 0 个元素的和”，初始值）
- S[1] = A[1] = 1（前 1 个元素的和）
- S[2] = A[1] + A[2] = 1 + 2 = 3（前 2 个元素的和）
- S[3] = A[1] + A[2] + A[3] = 1 + 2 + 3 = 6（前 3 个元素的和）
- S[4] = A[1] + A[2] + A[3] + A[4] = 1 + 2 + 3 + 4 = 10（前 4 个元素的和）
- S[5] = A[1] + A[2] + A[3] + A[4] + A[5] = 1 + 2 + 3 + 4 + 5 = 15（前 5 个元素的和）
所以，前缀和数组 S 就是 [0, 1, 3, 6, 10, 15]。
如何用前缀和数组计算区间和？¶
假设我们想计算原数组中从第 i 个元素到第 j 个元素的和（这里 i 和 j 是原数组的索引，且 1 ≤ i ≤ j ≤ n，n 是原数组长度）。
根据前缀和数组的定义：
- S[j] 是前 j 个元素的和（即 A[1] + A[2] + ... + A[j]）
- S[i-1] 是前 i-1 个元素的和（即 A[1] + A[2] + ... + A[i-1]）
那么，这两个和相减，就能得到从第 i 个到第 j 个元素的和：
区间和 = S[j] - S[i-1]
举个例子验证¶
用刚才的数组 A = [1, 2, 3, 4, 5]，计算区间 [2, 4]（即第 2 到第 4 个元素的和）：
- 原数组元素：A[2] = 2，A[3] = 3，A[4] = 4，和为 2 + 3 + 4 = 9
- 前缀和数组 S = [0, 1, 3, 6, 10, 15]
- 根据公式：S[4] - S[1] = 10 - 1 = 9，结果完全正确！
为什么前缀和这么快？¶
如果不用前缀和，每次计算区间和都需要从头加到尾，时间复杂度是 O(j - i + 1)（区间长度）。如果有 q 次查询，总时间就是 O(q * n)。
而用前缀和：
- 预处理前缀和数组的时间是 O(n)（遍历原数组一次）
- 每次查询区间和的时间是 O(1)（只需一次减法）
- 总时间复杂度是 O(n + q)，比直接计算快得多！
注意事项¶
- 索引对齐：要注意原数组和前缀和数组的索引对应关系。如果原数组是从 0 开始的（比如
A[0] = 1，A[1] = 2），前缀和数组的定义会稍有不同，但核心公式类似（此时区间和 = S[j+1] - S[i]）。 - 区间合法性：确保查询的区间
[i, j]有效（i ≥ 1，j ≤ n），否则会导致计算错误。 - 空间换时间：前缀和数组需要额外的空间存储，空间复杂度是 O(n)，但换来的是时间的极大优化。
总结¶
前缀和数组是一个简单又实用的数据结构，它通过“提前计算累积和”，将区间和的查询时间从 O(n) 降到 O(1)。核心思想是：用空间换时间，预处理一次，查询零次，非常适合处理“多次区间和查询”的问题。
现在，你是不是觉得前缀和数组变得简单易懂了？试着用自己的数组构造一个前缀和数组，然后计算几个区间和，感受一下它的神奇之处吧！