一、基本概念

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

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