2513 差分矩阵
大约 4 分钟
2513 差分矩阵
【算法】 二维差分
【C++】 二维数组、二维差分、scanf/printf
【难度】 普及/提高−
一、题目简述
行 列矩阵(), 次操作()。每次给子矩阵 到 每个元素加 。输出最终矩阵。
二、解题思路
数据规模分析
,矩阵有 个元素。如果每次操作都遍历子矩阵逐个加 ,单次最坏 , 次操作就是 ,铁定超时。
从一维差分到二维差分
一维差分回顾:给区间 加 :
diff[l] += c;
diff[r+1] -= c;操作完后做一次前缀和还原。
二维差分是其自然推广。给子矩阵 到 加 :
diff[x1][y1] += c;
diff[x1][y2+1] -= c;
diff[x2+1][y1] -= c;
diff[x2+1][y2+1] += c;图解标记
y1 y2+1
+-----+----------+-----+
| | | |
x1| | +c | -c |
| | | |
+-----+----------+-----+
| | | |
x2| | | |
| | | |
+-----+----------+-----+
x2+1 | -c | +c |
+-----+----------+-----+对 diff 数组做二维前缀和后,标记的效果自然扩散到整个子矩阵区域。+c 从 开始向右下传播,两个 -c 在右边界和下边界外抵消传播,右下角的 +c 补偿被两次抵消的部分。
算法步骤
- 读入原矩阵
- 对每次操作在
diff上做四点标记 - 对
diff做二维前缀和还原: - 输出
手动模拟
矩阵,初始:
1 2
3 4操作: 到 加 。
四点标记:
对 diff 做前缀和还原后,, , , 。
最终矩阵:
1+5=6 2+5=7
3+5=8 4+5=9与直接加 的结果一致。
操作: 到 加 。
四点标记:
前缀和还原后 , ,其余为 。
与原矩阵相加:
1+0=1 2+3=5
3+0=3 4+3=7正确。
输入输出优化
数据规模大,建议用 scanf / printf。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int a[N][N], diff[N][N];
int main() {
int n, m, q;
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &a[i][j]);
}
}
while (q--) {
int x1, y1, x2, y2, c;
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
diff[x1][y1] += c;
diff[x1][y2 + 1] -= c;
diff[x2 + 1][y1] -= c;
diff[x2 + 1][y2 + 1] += c;
}
// 二维前缀和还原差分
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1];
printf("%d ", a[i][j] + diff[i][j]);
}
printf("\n");
}
return 0;
}四、复杂度分析
- 时间复杂度:。每次操作用 做四点标记, 次操作后 做一次前缀和还原。总计约 ,非常安全。
- 空间复杂度:。两个 的
int数组约 MB。
五、易错点
- 数组下标从 1 开始,
y2+1和x2+1可能超出 和 ,所以数组要开到N = 1005(比数据范围多 5 格)。 - 二维差分的四点标记符号别弄反:左上
+c,右上-c,左下-c,右下+c。 - 最后输出是 ,不是单独的 (除非开始时把 合并到 中构建)。
六、扩展知识
差分与前缀和的关系
前缀和和差分互为逆运算。一维前缀和的逆是一维差分,二维前缀和的逆是二维差分。掌握一个,另一个就是反过来用。
合并原数组到差分数组
也可以将原数组直接合并到差分数组中构建,省一个数组:
// 读入时直接在 diff 上建初始差分(对单点 [i,j] 到 [i,j] 加 a[i][j])
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int x;
scanf("%d", &x);
diff[i][j] += x;
diff[i][j+1] -= x;
diff[i+1][j] -= x;
diff[i+1][j+1] += x;
}
}这样最终只需要对 diff 前缀和还原即可直接输出,无需保留原数组。但代码可读性会降低,建议初学者先用两个数组的写法。
类似题目
- 子矩阵求和:二维前缀和的基础应用
- 激光炸弹:二维前缀和 + 窗口枚举
