前缀和&差分
2026-04-25 13:32:32
发布于：广东
前缀和 & 差分笔记
一句话理解
前缀和：快速求出一段区间的和（预计算，直接查）
差分：快速对一段区间加上同一个数（记变化，最后算）
就像：
- 前缀和 = 你提前算出每个月累计花了多少钱，想知道某几个月花了多少，减一下就知道
- 差分 = 你在本子上记“从第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
前缀和怎么算？
int a[100], s[100];
s[0] = 0; // 第0个位置放0，方便计算
for (int i = 1; i <= n; i++) {
s[i] = s[i-1] + a[i];
}
前缀和有什么用？
求区间和超快！
想知道 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个学生的总分。
#include <iostream>
using namespace std;
int main() {
int a[6] = {0, 85, 90, 78, 92, 88}; // 下标1开始
int s[6];
// 计算前缀和
s[0] = 0;
for (int i = 1; i <= 5; i++) {
s[i] = s[i-1] + a[i];
}
// 求第2到第4个的和
int L = 2, R = 4;
int sum = s[R] - s[L-1];
cout << "第2到第4个学生的总分：" << sum << endl; // 输出 260
return 0;
}
二、差分
什么是差分？
差分：记录相邻两个数的差值。
差分数组 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
差分怎么算？
int a[100], d[100];
// 假设 a[0] = 0
for (int i = 1; i <= n; i++) {
d[i] = a[i] - a[i-1];
}
差分有什么用？
对一段区间统一加减超快！
要对 a[L] 到 a[R] 每个数都加上 x：
d[L] += x;
d[R+1] -= 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个数开始又变回原样
怎么从差分还原原数组？
int a[100], d[100];
a[0] = 0;
for (int i = 1; i <= n; i++) {
a[i] = a[i-1] + d[i];
}
实际例子：
差分数组 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次操作：
- 把第2到第4个数都加上10
- 把第3到第5个数都加上5
求最终的数组。
#include <iostream>
using namespace std;
int main() {
int a[6] = {0, 3, 5, 2, 8, 1};
int d[7] = {0}; // 差分数组，多开一个防止越界
int n = 5;
// 初始化差分数组
for (int i = 1; i <= n; i++) {
d[i] = a[i] - a[i-1];
}
// 操作1：第2到第4个数加10
d[2] += 10;
d[5] -= 10; // 5 = 4+1
// 操作2：第3到第5个数加5
d[3] += 5;
d[6] -= 5; // 6 = 5+1
// 还原最终数组
for (int i = 1; i <= n; i++) {
a[i] = a[i-1] + d[i];
}
// 输出结果
cout << "最终数组：";
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
cout << endl;
return 0;
}
运行过程：
原数组：[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
全部评论 2
张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！张kk牛逼！
2026-04-25 来自 广东
4
有帮助，赞一个