前缀和与差分的应用**
较难1前缀和与差分这对好兄弟，如何让区间操作变得飞快？
你是否遇到过这样的问题：老师想快速知道小明从周一到周五的零花钱总和，或者班长想统计全班同学某个矩形区域的考试总分？如果每次都一个一个地加，数据多了就会很慢。这时，前缀和和差分就能帮你轻松搞定——一个擅长快速求和，一个擅长快速修改，合起来简直是无敌组合！
一、先认识它们：前缀和和差分是什么？
想象你有一排存钱罐，每个罐子里有一定数量的硬币。要快速知道第2个到第5个罐子里有多少硬币，你可以先把所有罐子的硬币数记下来，然后“累计”出一个前缀和数组：pre[i] 表示前 i 个罐子的硬币总数。查询区间 [L, R] 的总和，直接用 pre[R] - pre[L-1]，瞬间得出答案。这就是前缀和——加速区间求和。
反过来，如果你想给第2到第5个罐子每个多放3个硬币，又不想一个一个修改，可以记录一个“增量标记”数组：在开始位置 +3，在结束的下一个位置 -3。这样，等所有操作完成后，再根据标记累加，就能得到每个罐子最终多放了多少。这个“标记数组”就是差分数组。它可以一次记录多个区间修改，最后统一处理。
核心关系：
- 差分负责“快速修改”（区间加/减）。
- 前缀和负责“快速查询”（区间求和）。
- 两者通常是先后出场的：先差分做修改，再前缀和做查询。
二、一维前缀和与一维差分：生活中的真实例子
1. 一维前缀和 —— 算零花钱
小明每天从周一到周日有零花钱，记录在数组 money 中（单位元）：
| 天 | 周一 | 周二 | 周三 | 周四 | 周五 | 周六 | 周日 |
|---|---|---|---|---|---|---|---|
| 零花钱 | 5 | 10 | 8 | 3 | 12 | 6 | 0 |
他想快速知道周三到周五（第3到第5天）的总零花钱。计算前缀和数组 pre，其中 pre[i] = pre[i-1] + money[i]。
pre[0] = 0pre[1] = 5pre[2] = 5+10=15pre[3] = 15+8=23pre[4] = 23+3=26pre[5] = 26+12=38- ...
查询区间[3,5]的总和：pre[5] - pre[2] = 38 - 15 = 23元。直接验证：8+3+12=23，正确！
# 一维前缀和小例子
money = [0, 5, 10, 8, 3, 12, 6, 0] # 下标1开始，第1天到第7天
n = 7
pre = [0] * (n + 1) # 前缀和数组，pre[0]=0
for i in range(1, n+1):
pre[i] = pre[i-1] + money[i]
L, R = 3, 5 # 查询周三到周五
total = pre[R] - pre[L-1] # 公式
print(f"第{L}天到第{R}天的零花钱总和为：{total}元")
2. 一维差分 —— 批量发红包
假设全班同学排队（1到N号），班长要给连续几号同学每人发一些作业本。比如：
- 给第2到第5号同学每人加3本。
- 再给第4到第7号同学每人加1本。
用差分数组可以一次记录，最后一起算出每人最终得到多少。差分数组 diff 初始全0，对于每个修改 [L, R] 加 val，执行：
diff[L] += val
diff[R+1] -= val
完成所有修改后，计算前缀和还原出每人实际增加值 add[i] = add[i-1] + diff[i]。
# 一维差分例子：同学编号1~8
n = 8
diff = [0] * (n + 2) # 多开一位防止越界
modifies = [(2, 5, 3), (4, 7, 1)] # 两次操作
for L, R, val in modifies:
diff[L] += val
diff[R+1] -= val
# 还原出每位同学得到的作业本数
add = [0] * (n + 1)
cur = 0
for i in range(1, n+1):
cur += diff[i]
add[i] = cur
print(f"第{i}号同学得到 {add[i]} 本")
输出：
第1号同学得到 0 本
第2号同学得到 3 本
第3号同学得到 3 本
第4号同学得到 4 本
第5号同学得到 4 本
第6号同学得到 1 本
第7号同学得到 1 本
第8号同学得到 0 本
三、应用1：先差分修改，再前缀和查询（组合拳）
这是最常见的用法。比如考试时，老师要记录每位同学每天练习的题量（初始都是0），然后每天会有一些同学在某个区间刷题。最后老师想知道任意连续几天里总共做了多少题。步骤如下：
- 用差分数组记录每次区间加题量的操作。
- 用前缀和还原出每天的实际题量。
- 对还原后的数组再求一次前缀和，以便快速回答任意区间总题量。
结合前面的例子：假设有8天，初始题量0。两次修改：[2,5]加3，[4,7]加1。最后查询区间[3,6]的总题量。代码实现如下：
n = 8 # 天数（从1开始编号）
# 差分数组，大小n+2以防R+1越界
diff = [0] * (n + 2) # 初始全0
# 多次区间修改：把[2,5]加3，[4,7]加1
modifies = [(2, 5, 3), (4, 7, 1)]
for L, R, val in modifies:
diff[L] += val
diff[R + 1] -= val
# 用前缀和还原成每天的实际题量 arr[1..n]
arr = [0] * (n + 1) # arr[0]闲置
cur = 0
for i in range(1, n + 1):
cur += diff[i]
arr[i] = cur
# 建立前缀和以便快速查询
pre = [0] * (n + 1)
for i in range(1, n + 1):
pre[i] = pre[i - 1] + arr[i]
# 查询区间[3,6]的总和
L_q, R_q = 3, 6
total = pre[R_q] - pre[L_q - 1]
print(f"区间[{L_q},{R_q}]的总和为：{total}")
运行结果：区间[3,6]的总和为：12
（验证：arr[3]=3, arr[4]=4, arr[5]=4, arr[6]=1, 和为3+4+4+1=12）
注意：原示例代码中注释写“输出8”是笔误，实际应为12。这里我们输出正确结果，但保留原意，作为提醒：写代码时要小心验证。
四、应用2：二维前缀和 —— 网格查询
你的班级座位排成了一个矩形，每个座位有同学的考试分数。老师想知道第 a 行到第 c 行、第 b 列到第 d 列（矩形区域）的总分。如果每次手动加，很慢。二维前缀和可以 O(1) 回答。
构造方法：
先按行计算每一行的前缀和，再按列累加，或者直接用递推公式：
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + grid[i][j]
查询左上角 (x1, y1) 到右下角 (x2, y2) 的矩形和：
sum = pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1]
举个例子：一个 3×3 的分数网格（行13，列13）：
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]
求第2行到第3行、第2列到第3列的矩形（即右下角2×2区域）的总和。
手工加：5+6+8+9=28。用二维前缀和验证：
# 二维前缀和示例
n, m = 3, 3
grid = [[0,0,0,0],
[0,1,2,3],
[0,4,5,6],
[0,7,8,9]] # 下标从1开始，第一行/列占位0
# 构造二维前缀和
pre = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + grid[i][j]
# 查询 (2,2) 到 (3,3)
x1, y1 = 2, 2
x2, y2 = 3, 3
total = pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1]
print(f"矩形区域的总分：{total}") # 输出 28
二维前缀和常用于图像处理、地图求和等问题，竞赛题中经常出现。
五、新手易犯的错误
-
数组大小搞错
- 一维差分数组至少需要
n+2个元素（索引从1到n+1均要用到）。如果只开n+1，当R=n时diff[R+1]会越界。 - 二维前缀和要注意行和列都从1开始，多开一行一列作为0边界。
- 一维差分数组至少需要
-
前缀和查询时边界混淆
- 一维：
pre[R] - pre[L-1]，注意L-1可能为0，要保证pre[0]已初始化为0。 - 二维：减的时候
pre[x1-1][y2]和pre[x2][y1-1]要加上pre[x1-1][y1-1]，别漏了。
- 一维：
-
差分操作顺序搞反
- 区间 [L,R] 加 val：
diff[L] += val，diff[R+1] -= val。不要写成diff[L] -= val或diff[R] += val。
- 区间 [L,R] 加 val：
-
忘记还原
- 差分只是记录“增量”，最终要累加才能得到实际值。不能直接用差分数组做前缀和查询（除非你已经还原过）。
六、完整可运行综合示例
下面是一个完整的 CP（竞赛）风格示例：先读入 n 和 m 次区间修改，再 q 次区间查询。包含输入、处理、输出。
"""
【题目模拟】有 n 天，初始作业量为0。有 m 次操作，每次给 [L,R] 增加 val。
然后有 q 次查询，每次询问 [L,R] 的总作业量。
用差分 + 前缀和解决。
"""
n = 8 # 天数
diff = [0] * (n + 2) # 差分数组，大小n+2
# 模拟输入：两次修改
modifies = [(2, 5, 3), (4, 7, 1)]
for L, R, val in modifies:
diff[L] += val
diff[R + 1] -= val
# 还原每天的值
arr = [0] * (n + 1)
cur = 0
for i in range(1, n + 1):
cur += diff[i]
arr[i] = cur
# 建前缀和
pre = [0] * (n + 1)
for i in range(1, n + 1):
pre[i] = pre[i - 1] + arr[i]
# 模拟查询
queries = [(3, 6), (2, 5), (1, 8)]
for L, R in queries:
total = pre[R] - pre[L - 1]
print(f"区间[{L},{R}]的和 = {total}")
输出：
区间[3,6]的和 = 12
区间[2,5]的和 = 14
区间[1,8]的和 = 16
你可以修改 modifies 和 queries 来测试不同情况。
七、延伸学习
- 前缀和与差分的推广：还可以处理二维矩阵的区间加（二维差分）和区间求和（二维前缀和）。
- 树状数组与线段树：如果既需要修改又需要查询，而且交替进行，可以用更高级的数据结构。
- 多次差分：比如对差分数组再做差分，可以实现区间加等差数列等操作。
掌握了前缀和和差分，你就拥有了快速处理区间问题的利器。很多看似复杂的问题，用这对“好兄弟”组合拳，就能变得简单高效！
例题精讲
给定一个长度为n的数组a（下标从1开始），定义前缀和数组pre满足pre[0]=0，pre[i]=pre[i-1]+a[i]（i≥1）。区间[l,r]的和（即a[l]+a[l+1]+...+a[r]）等于？
对于一个数组a，构造差分数组d，其中d[i]=a[i]-a[i-1]（i≥2），d[1]=a[1]。若要对原数组a的区间[l,r]每个元素加上x，只需要执行d[l]+=x，d[r+1]-=x（假设数组下标从1开始，且d的长度足够）。
以下Python函数用于构建一维前缀和数组，补全代码。
def build_prefix(a):
n = len(a)
pre = [0]*(n+1)
for i in range(1, n+1):
pre[i] = ___
return pre二维数组a（下标从1开始），定义二维前缀和pre[i][j]为左上角(1,1)到右下角(i,j)的子矩阵元素之和。则左上角(x1,y1)到右下角(x2,y2)的子矩阵和（其中x1≤x2，y1≤y2）为？
利用差分数组，可以在O(1)时间内完成对原数组任意区间各元素加同一个值的操作，但最终需要O(n)时间通过前缀和（或累加）将差分数组还原为原数组，才能得到修改后的数组。