前缀和 & 差分
一对对偶操作
前缀和(Prefix Sum)和差分(Difference)是互逆的:
原数组 a: 1 3 2 5 4
前缀和 s: 1 4 6 11 15 ← s[i] = a[0..i] 的和
差分 d: 1 2 -1 3 -1 ← d[i] = a[i] - a[i-1]| 擅长 | 单次操作 | |
|---|---|---|
| 前缀和 | 区间求和 | 预处理 |
| 差分 | 区间加 | 最后前缀和还原 |
核心口诀:
多次查询区间和 → 前缀和;多次区间修改 → 差分。
一维前缀和
定义
vector<long long> s(n + 1, 0); // s[0] = 0,1-indexed 更方便
for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i - 1];
// 查询 [l, r] 的和(1-indexed)
long long sum(int l, int r) { return s[r] - s[l - 1]; }为什么留 s[0] = 0:这样查询 [1, r] 就是 s[r] - s[0],不用特判 的边界。
a: [a1][a2][a3][a4][a5]
s: [0][a1][a1+a2][...][a1..a5]
sum(2,4) = s[4] - s[1] = (a1+a2+a3+a4) - (a1) = a2+a3+a4 ✓应用
| 问题 | 做法 |
|---|---|
| 区间和查询(静态) | 直接前缀和 |
| 平均值最大的子数组 | 前缀和 + 单调性 / 二分 |
| 和为 k 的子数组个数 | 前缀和 + 哈希表计数 |
| 是否存在和为 0 的子数组 | 前缀和 + 集合(两前缀和相等 ⟺ 中间和为 0) |
和为 k 的子数组个数
// sum(i, j] = s[j] - s[i] = k ⟺ s[i] = s[j] - k
long long count_subarray_sum(vector<int>& a, int k) {
unordered_map<long long, int> cnt;
cnt[0] = 1; // s[0] = 0 先放进去
long long s = 0, ans = 0;
for (int x : a) {
s += x;
ans += cnt[s - k]; // 有多少个 s[i] == s - k
cnt[s]++;
}
return ans;
}关键:cnt[0] = 1。否则会漏掉"从第 0 个元素开始"的子数组。
为什么能用哈希表:我们只关心"之前出现过几次某个前缀和值",不关心位置。这是 而不是。
二维前缀和
定义
即从 到 的矩形和。
构造(容斥)
┌───────────┬─────┐
│ │ │
│ s[i-1][j]│ s[i][j-1] 部分
│ │ │
├───────────┼─────┤ ← 重叠的 s[i-1][j-1] 被加了两次,减掉一次
│ │ a[i][j] │
└───────────┴─────────┘查询子矩阵 到
vector<vector<long long>> s(n + 1, vector<long long>(m + 1, 0));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];
long long query(int x1, int y1, int x2, int y2) {
return s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
}画个图就清楚了:大矩形减去上面和左边,被减两次的左上角加回来。
一维差分
定义
性质:对 求前缀和就还原回:
区间加
要给 全部:
d[l] += v ← 从这里开始,后面所有元素都 +v
d[r+1] -= v ← 到 r+1 抵消,后面的不受影响// 多次区间加,最后一次性还原
vector<long long> d(n + 2, 0); // 多开 1 个位置给 r+1
void add(int l, int r, long long v) { // 0-indexed
d[l] += v;
d[r + 1] -= v;
}
// 所有操作做完后:
for (int i = 1; i < n; i++) d[i] += d[i - 1];
// 现在 d[0..n-1] 就是最终数组为什么对: 的前缀和是。在 加 会让 全部;在 减 会把 及之后抵消回去。
复杂度: 次区间加 → 而不是。
典型题:区间覆盖次数
有 个区间,问每个位置被覆盖了多少次。
vector<int> d(n + 2, 0);
for (auto& [l, r] : intervals) { d[l]++; d[r + 1]--; }
for (int i = 1; i <= n; i++) d[i] += d[i - 1];
// d[i] 就是位置 i 的覆盖次数二维差分
同理,二维差分的前缀和是原数组。
矩形加
给矩形 到 全部:
d[x1][y1] += v
d[x1][y2+1] -= v
d[x2+1][y1] -= v
d[x2+1][y2+1] += vvoid add(int x1, int y1, int x2, int y2, long long v) {
d[x1][y1] += v;
d[x1][y2 + 1] -= v;
d[x2 + 1][y1] -= v;
d[x2 + 1][y2 + 1] += v;
}和二维前缀和的查询公式完全对称(把 和 对调),因为差分是前缀和的逆运算。
记忆方法:二维容斥的四个角,符号是 + - - +(左上角加,右上左下减,右下角加)。
进阶:带权/高阶前缀和
差分的高阶:多项式区间加
给 加上一个等差数列(如)。
用二阶差分:一次差分后再差分。
一次差分: d[l] += 1, d[r+1] -= 1 → 区间 +1
若要做 "区间加等差数列",需要维护一阶差分的差分实际实现:维护差分数组,区间加等差数列时:
// 给 [l, r] 加上首项 a、公差 d0 的等差数列
diff[l] += a;
diff[l + 1] += d0 - a;
diff[r + 1] -= a + (r - l) * d0;
diff[r + 2] -= d0 - (a + (r - l) * d0) ... // 容易写错这类题容易写错边界,更稳妥的做法是用线段树 + 懒标记,或者记住"做两次前缀和"的结构。
前缀和的变体
前缀最值
vector<int> pre(n), suf(n);
pre[0] = a[0];
for (int i = 1; i < n; i++) pre[i] = max(pre[i-1], a[i]);
suf[n-1] = a[n-1];
for (int i = n-2; i >= 0; i--) suf[i] = max(suf[i+1], a[i]);典型应用:
- 接雨水(每个位置能接多少 =
min(pre_max, suf_max) - h[i]) - 除自身以外数组的乘积(前缀积 × 后缀积)
- 股票买卖(从左到右扫最大收益)
前缀积(模意义下)
vector<long long> pre(n + 1, 1);
for (int i = 1; i <= n; i++) pre[i] = pre[i-1] * a[i-1] % MOD;
// 区间积 query(l, r) 需要逆元:
long long prod = pre[r] * qpow(pre[l-1], MOD-2, MOD) % MOD;需要模数是质数才能用费马小定理求逆元。或者用前缀积 + 后缀积避开逆元。
前缀异或和
性质:(因为)。
应用:子数组异或和为 0 ⟺ 两个前缀异或和相等。
树上前缀和
从根到节点的路径和(或路径上的某种累计量):
// dfs 时累计
void dfs(int u, int p, long long acc) {
pathSum[u] = acc + val[u];
for (int v : g[u]) if (v != p) dfs(v, u, pathSum[u]);
}两点路径上的和:
点权版本要用 LCA(见倍增章节)。
与其他数据结构的对比
| 需求 | 工具 | 单次复杂度 |
|---|---|---|
| 静态区间和 | 前缀和 | 查询, 预处理 |
| 区间加 + 单点查 | 差分 | 修改 |
| 单点加 + 区间和 | 树状数组 / 线段树 | |
| 区间加 + 区间和 | 线段树(懒标记) | |
| 多次区间加,最后统一查 | 差分 | 修改 + 收尾 |
选型的判断依据:
修改和查询是否交错?
- 全部修改在前、全部查询在后 → 差分(最快)
- 交替进行 → 树状数组 / 线段树这是最常用的优化:很多线段树题,如果离线处理,用差分就能 解决。
典型例题模式
1. 离线区间加 + 最后查询
// q 次操作"给 [l,r] 加 v",最后问每个位置的值
// → 差分,O(q + n)2. 区间和等于定值
// 前缀和 + 哈希表,O(n)3. 最大子数组和(Kadane / 前缀和)
// 前缀和视角:max over j of (s[j] - min_{i<j} s[i])
long long best = LLONG_MIN, minPre = 0, s = 0;
for (long long x : a) {
s += x;
best = max(best, s - minPre);
minPre = min(minPre, s);
}4. 矩阵区域和(多次查询)
// 二维前缀和,O(1) 查询5. 区间加 + 单点查询(多次交替)
// 差分 + 树状数组:把"区间加"变成差分数组上的"两个单点加"
// 把"单点查"变成差分数组上的"前缀和查询"
// → 树状数组 O(log n)这就是树状数组维护差分的技巧,兼顾了差分的简洁和动态查询。
常见坑
- 1-indexed vs 0-indexed 混乱:前缀和建议用
s[n+1],s[0]=0 s[r] - s[l-1]写成s[r] - s[l]:差一错误,最常见- 忘记
long long:前缀和是累加,很容易爆int( 个 的数累加 =) - 差分数组开太小:
d[r+1]会越界,要开n+2 - 二维容斥符号写错:记住
+ - - + - 哈希表的初始值:
cnt[0] = 1不能忘 - 差分还原时的范围:只还原到
n-1,d[n]是哨兵不用管 - 前缀和用于动态数组:数组会变时前缀和失效,要用树状数组
- 负数取模:前缀积/和涉及取模时,
(x % MOD + MOD) % MOD
许可协议:CC BY
作者:Davids
本文链接:https://hustjjd.github.io/bf1dd6df.html
更新于:2026年11月16日