前缀和与差分
2026-08-29 20:36:10
发布于：上海
前缀和与差分
1 一维前缀和
1.1 核心思想：空间换时间
前缀和指一个数组某下标之前的所有元素的和（即数列的前 $$n$$ 项和）。它是一种预处理，能把「快速求某一段的和」从 $$O(n)$$ 降到 $$O(1)$$。
原理：$$S[R]$$ 多拿了 $$[1, L-1]$$ 这一块，把 $$S[L-1]$$ 减掉就剩 $$[L,R]$$。
1.2 识别信号
- 关键词「区间和」 ：题目要求多次计算数组中某一段的和；
- 频繁查询：查询次数 $$m$$ 很大（如 $$10^5$$），$$n$$ 也很大——两重循环 $$O(nm)$$ 会炸，必须降到 $$O(n+m)$$；
- 静态数据：查询过程中不修改原数组元素。
1.3 构造：下标必须从 1 开始
为了处理 $$L=1$$ 的情况，前缀和必须让下标从 1 开始，并定义 $$S[0]=0$$。
s[0] = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
s[i] = s[i - 1] + a[i]; // 当前和 = 之前的总和 + 现在的自己
}
如果从 0 开始，查询 $$L=0$$ 时 $$S[L-1]$$ 就变成 $$S[-1]$$，直接越界。
1.4 完整模板
#include <iostream>
using namespace std;
long long a[100005], s[100005];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
s[i] = s[i - 1] + a[i]; // 预处理 O(n)
}
while (m--) {
int l, r;
cin >> l >> r;
cout << s[r] - s[l - 1] << endl; // 查询 O(1)
}
return 0;
}
1.5 应用：把最大子段和的暴力降一维
朴素求最大子段和是 $$O(n^3)$$（枚举左右端点 + 求和）。用前缀和后，求和变成 $$O(1)$$，整体降到 $$O(n^2)$$：
long long max_sum = -2e18;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
max_sum = max(max_sum, s[j] - s[i - 1]); // O(1) 拿到区间和
}
}
最大子段和的 $$O(n)$$ 解法见「线性DP」；这里演示的是前缀和作为通用降维工具的用法。
2 一维差分
2.1 核心思想：把区间修改变成两次单点修改
差分数组 $$d[i]$$ 表示原数组第 $$i$$ 位与第 $$i-1$$ 位的差值：
核心性质：差分数组的前缀和就是原数组——$$\sum_{j=1}^{i} d[j] = a[i]$$。
于是「把区间 $$[L,R]$$ 全部加上 $$v$$」等价于两次单点修改：
理解：$$d[L] += v$$ 代表从这里开始往后都涨了；$$d[R+1] -= v$$ 代表涨价到 $$R$$ 截止，$$R+1$$ 恢复原样。区间修改从 $$O(n)$$ 降到 $$O(1)$$。
2.2 识别信号
- 关键词「区间修改」 ：多次对某一段 $$[L,R]$$ 加减同一个数；
- 批量操作、最后才查询：给 $$m$$ 次修改，全做完才问数组变成什么样（或问最值、总和）；
- 不能中途查询：如果「修改—查询—修改」交替，差分就失效了（每次还原要 $$O(n)$$）——那时候该用树状数组或线段树。
2.3 构造与还原
// 初始化：直接按定义
for (int i = 1; i <= n; i++) d[i] = a[i] - a[i - 1];
// 区间修改
d[l] += v;
d[r + 1] -= v;
// 全部改完后，做一次前缀和还原
for (int i = 1; i <= n; i++) a[i] = a[i - 1] + d[i];
还原时注意：一定要先更新完 a[i] 再输出。差分建立的是项与项之间的联系，a[i] 依赖 a[i-1] 的新值；边算边用旧值会连环出错。
2.4 完整模板
#include <iostream>
using namespace std;
int d[100005], a[100005];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
d[i] = a[i] - a[i - 1]; // 初始化差分数组
}
while (m--) {
int l, r, v;
cin >> l >> r >> v;
d[l] += v; // 标准动作
d[r + 1] -= v;
}
for (int i = 1; i <= n; i++) {
a[i] = a[i - 1] + d[i]; // 还原
cout << a[i] << " ";
}
return 0;
}
3 前缀和与差分的关系
两者互为逆运算，就像求导与积分：先差分、再求前缀和，数组原样还原。
需求
用什么
复杂度
静态数组 + 频繁区间查询
前缀和
预处理 $$O(n)$$，查询 $$O(1)$$
频繁区间修改 + 最后统一查询
差分
修改 $$O(1)$$，还原 $$O(n)$$
又改又查（交替进行）
树状数组 / 线段树
均 $$O(\log n)$$
一句话：前缀和管「只读」，差分管「只写」，又读又写找树状数组。
4 二维前缀和
4.1 递推：容斥原理
口诀：加上区、加左区、减左上区、加当前格（加、加、减、加）。
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];
4.2 矩形区域查询
求以 $$(x_1,y_1)$$ 为左上角、$$(x_2,y_2)$$ 为右下角的矩形和：
口诀：减上块、减左块、加回重叠角（减、减、加）。
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];
}
别把两个公式记混：预处理是「加加减加」，查询是「减减加」。
4.3 反过来：从前缀和取出单个元素
这是 4.2 在 $$x_1=x_2=i,;y_1=y_2=j$$ 时的特例。
4.4 应用一：最大子矩阵（$$O(n^4)$$ 枚举）
枚举左上角和右下角，每个矩形用 4.2 的公式 $$O(1)$$ 求和：
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];
for (int x1 = 1; x1 <= n; x1++)
for (int y1 = 1; y1 <= m; y1++)
for (int x2 = x1; x2 <= n; x2++)
for (int y2 = y1; y2 <= m; y2++)
ans = max(ans, s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);
4.5 应用二：压缩列值（$$O(n^3)$$ 的更优解法）
上面的 $$O(n^4)$$ 还能再降一维：枚举上下边界，把中间这些行「压扁」成一维数组，再对这个一维数组求最大子段和。
这里只需要按列的前缀和（sum[i][j] = 第 $$j$$ 列前 $$i$$ 行的和）：
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
sum[i][j] = sum[i - 1][j] + a[i][j]; // 只对列做前缀和
for (int i = 1; i <= n; i++) { // 下边界
for (int k = 0; k < i; k++) { // 上边界（第 k+1 行到第 i 行）
memset(f, 0, sizeof(f));
memset(dp, 0, sizeof(dp));
for (int j = 1; j <= m; j++) {
f[j] = sum[i][j] - sum[k][j]; // 压缩后第 j 列的和
dp[j] = max(dp[j - 1] + f[j], f[j]); // 一维最大子段和
ans = max(ans, dp[j]);
}
}
}
思路本质：二维问题 → 固定两维（上下边界）→ 退化成一维经典问题。这是处理矩阵类题目的通用降维套路。
5 二维差分
5.1 矩形区域修改
把 $$(x_1,y_1)$$ 到 $$(x_2,y_2)$$ 的矩形全体加上 $$v$$，只需动四个角：
void update(int x1, int y1, int x2, int y2, int v) {
d[x1][y1] += v;
d[x2 + 1][y1] -= v;
d[x1][y2 + 1] -= v;
d[x2 + 1][y2 + 1] += v; // 容斥：多减的补回来
}
口诀：加（左上）、减（左下外）、减（右上外）、加（右下外） （加、减、减、加）。
理解：d[x1][y1] += v 让「从这里往右下」全部涨；后面三项负责把溢出到矩形外的部分裁掉，而右下角那块被裁了两次，所以要补回来一次。
5.2 还原
改完之后做一次二维前缀和就还原出结果矩阵：
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
ans[i][j] = ans[i - 1][j] + ans[i][j - 1] - ans[i - 1][j - 1] + d[i][j];
5.3 完整模板（洛谷 P3397 地毯）
这里空空如也
有帮助，赞一个