一维前缀和与差分
一、为什么要学习前缀和与差分？
对于一个数组，我们经常需要完成两种操作：
* 区间查询：求出从第 lll 个数到第 rrr 个数的总和。
* 区间修改：把从第 lll 个数到第 rrr 个数全部增加或减少某个值。
如果每次都用循环逐个处理，当数组很长、操作次数很多时，程序就会运行得很慢。
为了解决这两个问题，我们需要学习两种算法：
* 前缀和：快速计算一段区间的总和。
* 差分：快速给一段区间内的所有数加上同一个值。
二、前缀和
1. 什么是前缀和？
假设有一个数组：
a=[2,1,3,4,2]a=[2,1,3,4,2] a=[2,1,3,4,2]
现在需要计算前 4 个数的总和：
2+1+3+4=102+1+3+4=10 2+1+3+4=10
如果每次查询都重新相加，会做很多重复工作。
我们可以提前准备一个数组 preprepre，记录从第 1 个数开始，到当前位置为止的总和。
就像记账一样，每天都记录一下到今天为止一共花了多少钱，以后想知道某段时间花了多少，就不用重新计算每一天。
位置 iii 原数组 a[i]a[i]a[i] 前缀和 pre[i]pre[i]pre[i] 0 — 0 1 2 2 2 1 3 3 3 6 4 4 10 5 2 12
可以发现：
* 第 1 个位置的前缀和：222
* 第 2 个位置的前缀和：2+1=32+1=32+1=3
* 第 3 个位置的前缀和：2+1+3=62+1+3=62+1+3=6
每个位置的前缀和，都等于前一个位置的前缀和，加上当前位置的数。
因此：
pre[i]=pre[i−1]+a[i]\boxed{pre[i]=pre[i-1]+a[i]} pre[i]=pre[i−1]+a[i]
规定 pre[0]=0pre[0]=0pre[0]=0，表示前 0 个数的总和为 0。
2. 如何快速求区间和？
假设要求第 2 个数到第 4 个数的总和。
直接计算：
1+3+4=81+3+4=8 1+3+4=8
利用前缀和，可以换一种思路：
先计算前 4 个数的总和，再减去前 1 个数的总和。
(2+1+3+4)−2=8(2+1+3+4)-2=8 (2+1+3+4)−2=8
因此：
sum(l,r)=pre[r]−pre[l−1]\boxed{sum(l,r)=pre[r]-pre[l-1]} sum(l,r)=pre[r]−pre[l−1]
这里：
* pre[r]pre[r]pre[r]：从第 1 个数到第 rrr 个数的总和。
* pre[l−1]pre[l-1]pre[l−1]：区间左边那些不需要的数的总和。
两者相减，剩下的正好就是需要的区间。
这样无论区间有多长，查询时都只需要一次减法。
3. 前缀和代码
注意：
1. 数组从下标 1 开始，pre[0]pre[0]pre[0] 必须为 0。
2. 前缀和可能很大，建议使用 long long。
3. 前缀和适合数组不发生修改，或者先完成修改、再统一查询的情况。
4. 课堂练习
第 1 题：A83450 叫号机的区间统计
前缀和模板题。先计算前缀和数组，再利用区间求和公式回答每次查询。
第 2 题：A83453 大树下的阴凉处
寻找长度恰好为 kkk 的连续区间，使区间和最小。
思路：枚举每一个长度为 kkk 的区间，利用前缀和快速算出区间和，不断更新最小值。
三、差分
1. 什么是差分？
前缀和解决了快速查询区间和的问题。
现在考虑另一种情况：
给定一个数组，需要多次把一段连续区间内的所有数增加同一个值。
如果每次都使用循环，一个一个地修改，速度就会很慢。
差分可以让我们只修改两个位置，就表示出整个区间的变化。
2. 差分的基本思想
可以把差分想象成一排学生的加分记录。
老师要求从第 2 名到第 4 名学生，每个人增加 3 分。
没有必要提前把这 3 个人的成绩全部修改一遍，只需要做两个标记：
* 在第 2 名学生的位置标记 +3+3+3，表示从这里开始加分。
* 在第 5 名学生的位置标记 −3-3−3，表示从这里开始取消加分。
之后从左往右累计这些标记，就能知道每个人应该增加多少分。
假设原来的 5 个数都是 0。
位置 1 2 3 4 5 原数组 0 0 0 0 0 差分标记 0 +3 0 0 -3 累加结果 0 3 3 3 0
可以看到，第 2、3、4 个位置都增加了 3，其余位置保持不变。
因此，如果需要把区间 [l,r][l,r][l,r] 中的数全部增加 ccc，只需要：
d[l]+=c\boxed{d[l]+=c} d[l]+=c
d[r+1]−=c\boxed{d[r+1]-=c} d[r+1]−=c
注意：一定是 r+1r+1r+1，而不是 rrr！
因为第 rrr 个位置仍然需要增加 ccc，到了第 r+1r+1r+1 个位置才应该取消。
3. 如何构造差分数组？
如果原数组本来就有数值，就需要先构造差分数组。
差分数组记录的是当前位置与前一个位置相差多少。
例如：
a=[2,5,4,7]a=[2,5,4,7] a=[2,5,4,7]
对应的差分数组为：
d=[2,3,−1,3]d=[2,3,-1,3] d=[2,3,−1,3]
因为：
* 第 1 个位置：222
* 第 2 个位置：5−2=35-2=35−2=3
* 第 3 个位置：4−5=−14-5=-14−5=−1
* 第 4 个位置：7−4=37-4=37−4=3
因此：
d[i]=a[i]−a[i−1]\boxed{d[i]=a[i]-a[i-1]} d[i]=a[i]−a[i−1]
其中，规定 a[0]=0a[0]=0a[0]=0。
4. 如何还原原数组？
差分数组只记录相邻位置之间的变化，并不是最终的数值。
想恢复原数组，只需要从左往右不断累加。
例如：
d=[2,3,−1,3]d=[2,3,-1,3] d=[2,3,−1,3]
还原的过程：
a[1]=2a[1]=2 a[1]=2
a[2]=2+3=5a[2]=2+3=5 a[2]=2+3=5
a[3]=2+3−1=4a[3]=2+3-1=4 a[3]=2+3−1=4
a[4]=2+3−1+3=7a[4]=2+3-1+3=7 a[4]=2+3−1+3=7
因此：
a[i]=a[i−1]+d[i]\boxed{a[i]=a[i-1]+d[i]} a[i]=a[i−1]+d[i]
是不是很熟悉？
差分数组通过前缀和，就能还原原数组。
这就是前缀和与差分之间最重要的联系。
5. 差分代码
注意：
1. 数组从 1 开始，a[0]=0a[0]=0a[0]=0。
2. 差分数组需要多开一个位置，保证 d[n+1]d[n+1]d[n+1] 不会越界。
3. 区间修改时不需要直接修改原数组。
4. 所有区间修改完成后，再利用前缀和还原结果。
6. 课堂练习
第 3 题：A83456 最多涂色次数
每次给一段区间涂色，求被涂色次数最多的位置的涂色次数。
思路：每个区间都在起点增加 1，在终点的下一个位置减少 1。最后求前缀和，并找出最大值。
注意题目中的坐标起点，避免下标错误。
第 4 题：A83455 考试补分
对已有的成绩数组进行多次区间加分，求最后的最低成绩。
思路：
1. 根据原始成绩构造差分数组。
2. 使用差分进行多次区间修改。
3. 还原最终成绩数组。
4. 遍历数组，找到最小值。
四、前缀和与差分的区别
对比 前缀和 差分 主要作用 快速查询区间和 快速修改整个区间 预处理 不断累加 与前一个数相减 核心操作 两个前缀和相减 修改区间的两个边界 后续处理 直接回答查询 最后通过前缀和还原 常见题型 多次区间求和 多次区间加减
可以用两句话记住：
前缀和：提前算好累计结果，需要哪一段就减出来。
差分：先标记哪里开始变化、哪里结束变化，最后统一累加。
它们之间还有一个重要关系：
* 原数组经过差分，可以得到差分数组。
* 差分数组经过前缀和，可以恢复原数组。
五、时间复杂度
假设数组长度为 nnn，有 qqq 次操作。
普通循环每次处理整个区间，最坏可能需要处理 nnn 个位置。
使用前缀和：
* 建立前缀和数组：O(n)O(n)O(n)
* 查询一次区间和：O(1)O(1)O(1)
使用差分：
* 建立差分数组：O(n)O(n)O(n)
* 修改一次区间：O(1)O(1)O(1)
* 最后还原数组：O(n)O(n)O(n)
因此，当操作次数很多时，前缀和与差分能够明显减少重复计算。
六、课后作业
基础巩固（必做）
1. A83452 双前缀求和
知识点：排序、前缀和。
按照题目要求建立两套前缀和数组，再利用相应的前缀和回答查询。
2. A83451 字符串相邻统计
知识点：前缀和的灵活应用。
先判断每个相邻位置是否满足条件，满足记为 1，不满足记为 0，再建立前缀和进行区间统计。
综合提高（选做）
3. A46042 买凤梨2
知识点：差分 + 前缀和。
这道题需要把两个知识点结合起来：
1. 使用差分，统计每个位置被推荐的次数。
2. 判断每个位置的推荐次数是否达到要求，满足记为 1，否则记为 0。
3. 对新的 0/1 数组建立前缀和。
4. 利用前缀和回答区间查询。
七、本节课总结
学完本节课，需要掌握以下四个核心公式。
1. 建立前缀和
pre[i]=pre[i−1]+a[i]\boxed{pre[i]=pre[i-1]+a[i]} pre[i]=pre[i−1]+a[i]
2. 查询区间和
sum(l,r)=pre[r]−pre[l−1]\boxed{sum(l,r)=pre[r]-pre[l-1]} sum(l,r)=pre[r]−pre[l−1]
3. 差分区间加法
d[l]+=c,d[r+1]−=c\boxed{d[l]+=c,\quad d[r+1]-=c} d[l]+=c,d[r+1]−=c
4. 根据差分还原数组
a[i]=a[i−1]+d[i]\boxed{a[i]=a[i-1]+d[i]} a[i]=a[i−1]+d[i]
最后记住：
前缀和解决区间查询，差分解决区间修改。
前缀和是累加，差分是相减。
看到多次区间求和，优先考虑前缀和；看到多次区间加减、最后统一求结果，优先考虑差分。
