前缀和**

什么是前缀和？——快速计算区间总和的“魔法盒子”

想象一下，你每天攒下零花钱，想知道从第3天到第7天一共攒了多少钱。如果每次都要把这几天的钱重新加一遍，那多麻烦呀！前缀和就是帮你提前算好每一天之前（包括当天）的累计金额，之后无论问哪几天的总和，都能瞬间算出来。

它常用于解决区间求和问题——比如统计班级分数段、商场某几天的销售额、游戏里连续关卡的得分等。核心思想是**“预处理 + O(1)查询”**，让程序跑得飞快。

一步一步认识前缀和

1. 什么是前缀和数组？

假设有一个原始数组 scores，里面存放着10个同学的数学成绩（编号从1到10）：

位置:   1   2   3   4   5   6   7   8   9  10
分数:  85  92  78  90  88  95  70  82  91  89

我们定义一个新的数组 pre，其中 pre[i] 表示从第1个位置到第i个位置的所有分数的总和。比如：

• pre[1] = 第1个分数 = 85
• pre[2] = 第1个 + 第2个 = 85 + 92 = 177
• pre[3] = 前三个分数和 = 85 + 92 + 78 = 255
• ……
• pre[10] = 全部10个分数之和 = 850

为了方便计算，我们通常令 pre[0] = 0，这样 pre[i] 就正好是前 i 个数的和。

2. 怎么生成前缀和数组？

利用递推关系：pre[i] = pre[i-1] + scores[i-1]（注意数组下标从0开始，这里scores下标要减1）。

用代码写出来很简单：

scores = [85, 92, 78, 90, 88, 95, 70, 82, 91, 89]  # 原始分数
n = len(scores)  # 人数

# 构建前缀和数组，长度比原数组多1，pre[0]=0
pre = [0] * (n + 1)
for i in range(n):
    pre[i + 1] = pre[i] + scores[i]

print(pre)  # 输出: [0, 85, 177, 255, 345, 433, 528, 598, 680, 771, 860]

你看，pre[3] 是 255，正好是前3个分数 85+92+78 = 255。

3. 如何用前缀和快速求任意区间总和？

假设老师想知道第3个到第7个同学的总分（从第3个到第7个，共5个人）。传统方法：78+90+88+95+70 = 421。

用前缀和就简单了：区间 [L, R] 的总和 = pre[R] - pre[L-1]。

这里 L=3，R=7，那么：

• pre[7] = 前7个数的和 = 85+92+78+90+88+95+70 = 598
• pre[2] = 前2个数的和 = 85+92 = 177
• 区间和 = 598 - 177 = 421

神奇吧！只要一次减法，不管区间多长，速度都一样快。

为什么公式是 pre[R] - pre[L-1]？
因为 pre[R] 包含了第1到第R个，pre[L-1] 包含了第1到第L-1个，相减正好剩下第L到第R个。

生活中的更多例子

1. 零花钱统计：小明每天存零花钱，想知道本月第5天到第15天一共存了多少。如果每天记录一个前缀和，直接相减就行。
2. 游戏得分：打游戏获得经验值，想知道第3关到第8关的总得分，用前缀和秒算。
3. 商场销量：超市记录了每天酸奶的销售额，想算每周三到周六的总销售额，直接套公式。

新手常犯的错误

1. 数组下标搞混
   很多人把原始数组下标和前缀和数组下标弄反。记住：pre[0] 对应 0 个数的和，pre[1] 对应第1个数，pre[5] 对应前5个数。在计算区间 [L,R] 时，L 和 R 通常从1开始，但编程中原始数组往往从0开始，因此需要小心映射。

2. 忘记 pre[0] 的存在
   如果直接让 pre 数组长度等于 n，那么 pre[L-1] 在 L=1 时会越界（因为 L-1=0 需要存在）。所以一定要设置 pre[0] = 0，并让 pre 长度为 n+1。

3. 区间 L 大于 R
   如果有人问“第7到第3个同学的总分”，这没有意义。编程时要注意检查 L <= R。

4. 前缀和计算时的循环范围
   构建前缀和时，循环是 for i in range(n)，然后 pre[i+1] = pre[i] + scores[i]，不要写成 pre[i] = pre[i-1] + scores[i]（这样 i=0 时会出错）。

完整可运行的代码示例

下面是一个完整的程序，演示了如何构建前缀和，并多次查询不同区间：

# 原始分数数组（第0个位置对应第1个同学）
scores = [85, 92, 78, 90, 88, 95, 70, 82, 91, 89]
n = len(scores)  # 人数

# 构建前缀和数组 pre[0]=0
pre = [0] * (n + 1)
for i in range(n):
    pre[i + 1] = pre[i] + scores[i]

# 定义查询区间（L,R从1开始）
queries = [(3, 7), (1, 5), (6, 9), (2, 8)]

for L, R in queries:
    total = pre[R] - pre[L - 1]  # 核心公式
    print(f"第{L}到第{R}个同学的总分是：{total}")

运行结果：

第3到第7个同学的总分是：421
第1到第5个同学的总分是：433
第6到第9个同学的总分是：338
第2到第8个同学的总分是：595

你可以自己验算一下，比如第1到第5个：85+92+78+90+88 = 433，正确！

相关知识点指引

• 二维前缀和：如果数据是表格（比如全班同学的座位，每个格子有分数），想求一个矩形区域的总和，就需要二维前缀和。它的思想类似，只是从一维扩展到二维。
• 差分数组：前缀和的“逆运算”。如果你要频繁给某个区间统一加上一个数（比如给第3到第7个同学每人加5分），用差分可以高效完成，最后再用前缀和还原。
• 前缀积：有时需要快速计算连续乘积，可以类似地构建前缀积（要注意积可能很大，常用模运算）。
• 哈希表优化：前缀和不只用于求和，还常用于统计满足条件的子数组个数（比如连续子数组和为 k 的个数），结合哈希表可以快速解决很多经典题目。

掌握前缀和，就像给计算加了“加速器”，让你在比赛中更快更准地得到答案。试试用前缀和解决你编程题中的区间求和问题吧！