- C++
前缀和 + 差分 C++ 教程(GESP五级)
- @ 2026-10-21 23:07:11
前缀和 + 差分 C++ 教程(GESP五级)
前置:数组、循环 核心定位:快速求一段区间的和、快速给一段区间统一加减数字 重点:数学原理、什么时候用、为什么比循环快、代码、背诵口诀、坑点
一、前缀和
1. 数学道理
原数组 a[1],a[2],a[3]...a[n]
前缀和数组 s,规定:
👉 s[i]:前 i 个数全部加起来的总和
区间求和公式(最重要!) 求从 l 到 r 这个区间所有数字的和:
举例子: a = [0, 5, 2, 7, 1] (下标从1开始) (s[0] = 0) s[1]=5 s[2]=5+2=7 s[3]=5+2+7=14 s[4]=5+2+7+1=15
求 l=2,r=3(a[2]+a[3] = 2+7=9)
s[3]-s[1] = 14 - 5 = 9 ✔
✅ 优势: 普通做法:每次查询区间和,for循环一遍 l~r。如果查询很多次,很慢。 前缀和:先花一次时间预处理s数组,之后每一次区间求和,只需要一次减法 O(1)
一句话:预处理一次,查询随便秒算。
2. 前缀和完整代码,逐行注释
#include <iostream>
using namespace std;
const int N = 100010; // 数组最大长度
int a[N], s[N]; // a原数组,s前缀和数组
int main()
{
int n, q;
cin >> n >> q; // n数字个数,q次查询
for(int i = 1; i <= n; i++)
{
cin >> a[i];
}
// 预处理前缀和
s[0] = 0;
for(int i = 1; i <= n; i++)
{
s[i] = s[i-1] + a[i];
}
// 处理q次区间查询
while(q--)
{
int l, r;
cin >> l >> r;
cout << s[r] - s[l-1] << endl;
}
return 0;
}
📖 背诵口诀(前缀和)
- 下标从1开始,(s[0] = 0)
s[i] = s[i-1] + a[i]- 区间 l~r 和:
s[r] - s[l-1]
⚠️ 大坑:l不能写成 s[l],一定是 l-1!
二、差分(差分数组)
1. 数学道理(配合前缀和理解)
差分是前缀和的逆操作!
需求:给区间 [l, r] 里面每一个数都加上一个数 d
如果直接循环 l~r 一个个加,区间很大、修改次数很多的时候很慢。
差分数组 b:
性质:b数组的前缀和,就是原数组a。
差分修改公式:
b[l] += d;
b[r+1] -= d;
修改全部做完之后,对b求一遍前缀和,就得到修改后的a数组!
举例: 原数组 a:[0, 1,2,3,4] b初始全0 我们要:l=2,r=3,全部 +5
b[2] +=5
b[4] -=5
之后求b的前缀和: b前缀:0,5,5,0 得到 a:1, 2+5,3+5,4 ✔ 只有2、3位置加上了5,完美。
✅ 优势: 一次区间加操作,只改两个位置 O(1)。 所有修改做完,最后只跑一遍前缀和还原数组。
一句话记忆差分:一加一减,最后跑前缀和还原。
2. 差分完整代码,逐行注释
#include <iostream>
using namespace std;
const int N = 100010;
int a[N], b[N]; // a原数组,b差分数组
// 差分插入函数:给[l,r]加上d
void insert(int l, int r, int d)
{
b[l] += d;
b[r+1] -= d;
}
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
insert(i, i, a[i]); // 初始化差分:相当于a[i]放到b
}
// m次区间修改:l r d
while(m--)
{
int l, r, d;
cin >> l >> r >> d;
insert(l, r, d);
}
// 对差分数组求前缀和,得到修改后的数组
for(int i = 1; i <= n; i++)
{
b[i] = b[i-1] + b[i];
cout << b[i] << " ";
}
return 0;
}
📖 背诵口诀(差分)
- 差分核心函数:
b[l]+=d; b[r+1]-=d; - 所有修改做完,对b跑前缀和
- 结果就是修改完成的数组
⚠️ 大坑:r+1 不能越界!r等于n的时候,r+1是n+1,数组要开大一点。
三、前缀和 vs 差分对比(板书)
| 算法 | 擅长干什么 | 操作 | 流程 |
|---|---|---|---|
| 前缀和 | 多次查询【区间求和】 | 预处理一次前缀和,查询减法 | 先预处理,再查询 |
| 差分 | 多次【区间统一加/减】,最后看数组 | 每次修改只改两点,最后前缀和还原 | 先全部修改,最后还原 |
区分一句话: 问区间总和 → 前缀和 给一段区间集体加数字 → 差分
四、极简手动模拟(n=4)
a = [1,2,3,4]
差分b初始0
操作:l=2 r=3 d=+5
b[2]+=5,b[4]-=5
b数组:[0,0,5,0,-5]
求前缀和:
i=1:0 →1
i=2:0+5=5 →2+5
i=3:5+0=5 →3+5
i=4:5-5=0 →4
五、配套课堂小练习
- 前缀和:a=[3,1,4,2], 求 l=2,r=4 的和
- 差分:数组 [10,20,30,40],执行 l=1,r=3 全部+2,写出b数组变化和最终数组
答案
- s[4]-s[1] = (3+1+4+2)-3 = 7
- b[1]+=2,b[4]-=2;最终:12,22,32,40
六、拓展提醒(GESP考点)
前缀和、差分默认下标从1开始,避开0的麻烦,是竞赛约定写法。 二维前缀和、二维差分是进阶,五级先吃透一维。