前缀和 & 差分笔记
一句话理解
前缀和：快速求出一段区间的和（预计算，直接查）
差分：快速对一段区间加上同一个数（记变化，最后算）
就像：
* 前缀和 = 你提前算出每个月累计花了多少钱，想知道某几个月花了多少，减一下就知道
* 差分 = 你在本子上记“从第3天到第7天每天多花10元”，最后再统一算总账
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
一、前缀和
什么是前缀和？
前缀和：从第一个数到当前位置的累计和。
设原数组为 a[1], a[2], a[3], ..., a[n]
前缀和数组 s[i] = a[1] + a[2] + ... + a[i]
实际例子：
原数组：a[1]=3, a[2]=5, a[3]=2, a[4]=8, a[5]=1
前缀和：s[1]=3, s[2]=8, s[3]=10, s[4]=18, s[5]=19
解释：
s[1] = 3
s[2] = 3+5 = 8
s[3] = 3+5+2 = 10
s[4] = 3+5+2+8 = 18
s[5] = 3+5+2+8+1 = 19
前缀和怎么算？
前缀和有什么用？
求区间和超快！
想知道 a[L] 到 a[R] 的和：
区间和 = s[R] - s[L-1]
实际例子：
求 a[3] 到 a[5] 的和
a[3]=2, a[4]=8, a[5]=1 加起来 = 11
用公式：s[5] - s[2] = 19 - 8 = 11
再举个例子：
求 a[2] 到 a[4] 的和
a[2]=5, a[3]=2, a[4]=8 加起来 = 15
用公式：s[4] - s[1] = 18 - 3 = 15
对比效率：
方法 每次查询时间 做100次查询 直接加 O(n) 100×n 步 前缀和 O(1) 100 步
完整代码例子
题目：有5个学生的成绩 [85, 90, 78, 92, 88]，求第2个到第4个学生的总分。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、差分
什么是差分？
差分：记录相邻两个数的差值。
差分数组 d[i] = a[i] - a[i-1]
实际例子：
原数组：a[1]=3, a[2]=5, a[3]=2, a[4]=8, a[5]=1
计算差分：
d[1] = a[1] - a[0] = 3 - 0 = 3
d[2] = a[2] - a[1] = 5 - 3 = 2
d[3] = a[3] - a[2] = 2 - 5 = -3
d[4] = a[4] - a[3] = 8 - 2 = 6
d[5] = a[5] - a[4] = 1 - 8 = -7
差分数组：d[1]=3, d[2]=2, d[3]=-3, d[4]=6, d[5]=-7
差分怎么算？
差分有什么用？
对一段区间统一加减超快！
要对 a[L] 到 a[R] 每个数都加上 x：
实际例子：
原数组：a = [3, 5, 2, 8, 1]
要对 a[2] 到 a[4] 每个数都加 10
操作：
d[2] += 10
d[5] -= 10
原理：
* 加在 L=2 位置：从第2个数开始后面所有数都会被影响
* 减在 R+1=5 位置：从第5个数开始又变回原样
怎么从差分还原原数组？
实际例子：
差分数组 d = [3, 2, -3, 6, -7]
还原：
a[1] = a[0] + d[1] = 0 + 3 = 3
a[2] = a[1] + d[2] = 3 + 2 = 5
a[3] = a[2] + d[3] = 5 + (-3) = 2
a[4] = a[3] + d[4] = 2 + 6 = 8
a[5] = a[4] + d[5] = 8 + (-7) = 1
得到原数组 [3, 5, 2, 8, 1]
完整代码例子
题目：有5个数 [3, 5, 2, 8, 1]，进行2次操作：
1. 把第2到第4个数都加上10
2. 把第3到第5个数都加上5
求最终的数组。
运行过程：
原数组：[3, 5, 2, 8, 1]
第一次加10后：[3, 15, 12, 18, 1]
第二次加5后：[3, 15, 17, 23, 6]
最终输出：3 15 17 23 6
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、对比总结
对比项 前缀和 差分 核心思想 预计算累计和 记录相邻差值 主要用途 快速求区间和 快速区间加减 预处理 O(n) O(n) 操作时间 查询 O(1) 区间加 O(1) 怎么得到 s[i] = s[i-1] + a[i] d[i] = a[i] - a[i-1] 怎么还原 直接查 s 数组 a[i] = a[i-1] + d[i]
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、记忆口诀
前缀和，预存和，区间和，一减得
差分记，差的值，区间加，两端改
前缀和：s[r] - s[l-1] 就是区间和
差分：d[l] += x，d[r+1] -= x，最后前缀和还原
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、小测验
第1题：数组 a = [2, 4, 6, 8, 10]，前缀和 s[4] 是多少？
答案：s[4] = 2+4+6+8 = 20
第2题：用前缀和求 a[2] 到 a[4] 的和，公式是什么？
答案：s[4] - s[1]
第3题：要对 a[3] 到 a[7] 每个数加 5，差分数组怎么改？
答案：d[3] += 5，d[8] -= 5
第4题：差分数组 d = [2, 1, 3, 2]，还原后的 a[3] 是多少？（设 a[0]=0）
答案：
a[1] = 0+2 = 2
a[2] = 2+1 = 3
a[3] = 3+3 = 6
答案是 6
