二维数组的差分
一、基本概念
二维数组差分是一种高效处理区间修改操作的数据结构技巧，常用于解决矩阵区域增减问题。
差分是前缀和的逆运算，对于二维数组，差分数组 diff[i][j] 表示原数组 a[i][j] 与 a[i-1][j] + a[i][j-1] - a[i-1][j-1] 的差值。
二维差分是处理子矩阵增减操作的高效方法。
原矩阵：
a[i][j](1 ≤ i ≤ m, 1 ≤ j ≤ n)差分矩阵：
b[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]
二、核心性质
差分矩阵的前缀和就是原矩阵
子矩阵增减操作：
给以
(x1,y1)为左上角，(x2,y2)为右下角的子矩阵每个元素加c：
b[x1][y1] += c b[x2+1][y1] -= c b[x1][y2+1] -= c b[x2+1][y2+1] += c
因为差分数组的前缀和相当于原数组，所以对差分数组进行以上四个单点操作后，就相当于给原数组数组的区块加上一个值 c
（1）构建方式
//求出差分数组
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
}
}（2）增减操作
void add(int x1,int y1,int x2,int y2,int c)
{
b[x1][y1] += c; // 影响从(x1,y1)开始的所有区域
b[x2 + 1][y1] -= c; // 消除x方向超出范围的影响
b[x1][y2 + 1] -= c; // 消除y方向超出范围的影响
b[x2 + 1][y2 + 1] += c; // 补偿多减去的区域（容斥原理）
}(3)还原操作
b[i][j] += b[i-1][j] + b[i][j-1] - b[i-1][j-1];
四、参考代码
#include <iostream>
using namespace std;
int a[100][100]; // 原始数组
int b[100][100]; // 差分数组
int res[100][100]; // 结果数组
// 区域增加操作
void rangeAdd(int x1, int y1, int x2, int y2, int c) {
b[x1][y1] += c;
b[x1][y2+1] -= c;
b[x2+1][y1] -= c;
b[x2+1][y2+1] += c;
}
// 从差分数组还原原数组
void restoreArray(int m, int n) {
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
res[i][j] = res[i-1][j] + res[i][j-1] - res[i-1][j-1] + b[i][j];
}
}
}
int main() {
int m, n, c;
cin >> m >> n;
// 1. 先输入原始数组的值
cout << "请输入" << m << "行" << n << "列的矩阵:" << endl;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
// 2. 构建差分数组
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
b[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1];
}
}
// 3. 输入修改参数
cout << "请输入要增加的值c和区域(x1,y1)-(x2,y2):" << endl;
int a1, b1, a2, b2;
cin >> c >> a1 >> b1 >> a2 >> b2;
// 4. 执行区域增加操作
rangeAdd(a1, b1, a2, b2, c);
// 5. 还原数组
restoreArray(m, n);
// 6. 输出结果
cout << "修改后的数组:" << endl;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cout << res[i][j] << " ";
}
cout << endl;
}
return 0;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
