一、基本概念

二维数组差分是一种高效处理区间修改操作的数据结构技巧，常用于解决矩阵区域增减问题。

差分是前缀和的逆运算，对于二维数组，差分数组 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]

二、核心性质

1. 差分矩阵的前缀和就是原矩阵

2. 子矩阵增减操作：

• 给以 (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;
}