二维差分

  1 /*
  2     二维差分的实际例题，差分演化
  3     数据输入样例：
  4     3 4 3
  5     1 2 2 1
  6     3 2 2 1
  7     1 1 1 1
  8     1 1 2 2 1
  9     1 3 2 3 2
 10     3 1 3 4 1
 11 
 12 
 13     3 4 3       规模：三行四列，经过三次操作
 14     1 2 2 1
 15     3 2 2 1
 16     1 1 1 1     三行四列的数组
 17     1 1 2 2 1   针对x1,y1到x2,y2之间增加一个c，这里就是针对(1,1)到(2,2)之间增加1的意思
 18     1 3 2 3 2
 19     3 1 3 4 1
 20 
 21 */
 22 
 23 #include <iostream>
 24 using namespace std;
 25 /*
 26     1e3 是一个科学计数法表示的浮点数，等于 1 * 10^3，也就是 1000.0
 27     由于 1e3 是浮点数，而 10 是整数，C++会进行隐式类型转换，
 28     将 10 转换为浮点数 10.0，然后再进行加法运算。
 29     由于 N 是 int 类型，而 1e3 + 10 是浮点数类型，C++会进行隐式类型转换，
 30     将 1010.0 转换为整数 1010，然后将其存储在 N 中
 31 */
 32 //const int N = 1e3 + 10;
 33 const int N = 10;
 34 int n, m, q;
 35 int a[N][N], b[N][N];
 36 
 37 void insert(int x1, int y1, int x2, int y2, int c) {
 38     // 差分数组为什么用下面的公式就可以计算出来，可以参考如下视频：
 39     // https://www.bilibili.com/video/BV1Et421L7AY?t=1275.5
 40     b[x1][y1] += c;                    
 41     b[x1][y2 + 1] -= c;
 42     b[x2 + 1][y1] -= c;
 43     b[x2 + 1][y2 + 1] += c;
 44 }
 45 
 46 int main() {
 47     cin >> n >> m >> q;
 48     for (int i = 1; i <= n; i++)
 49         for (int j = 1; j <= m; j++) {
 50             cin >> a[i][j];              //  输入原始数组数据
 51             /*
 52              初始化上述数组a的同时就可以开始进行下面差分数组b的初始化了，
 53              由于a和b初始化数据都是0，因此，原始数组a的差分数组初始化的时候就是b数组，
 54             上述输入a[i][j]的值以后，就相当于对a[i][j]进行增量操作，这种增量操作
 55             可以通过差分数组b来完成，也就是相当于对区域 b(i,j)到b(i,j)同时增加一个 a[i][j]
 56             下面调用insert方法时，需要在原始数组里更新的起止两个单元格的坐标一样，也就是x1=x2,y1=y2，
 57             就相当于对本单元格进行批量更新操作，那么insert方法按照差分数组此时的修改规则来修改四个单元格里的值了
 58             这里的理解重点是：1. 初始化时，由于所有元素都是0，b数组就已经是a数组的差分数组了；
 59             2. a数组每个单元格进行手工输入初始化时(上述cin >> a[i][j])，就相当于对每个单元格进行更新操作；
 60             3. insert方法就是按照差分数组的更新公式对四个单元格进行更新。
 61             */
 62             insert(i, j, i, j, a[i][j]);
 63         }
 64     cout<<endl;
 65     // 上述初始化原数组a的同时，也初始化了差分数组b，差分数组b是怎么计算出来的，可以参考如下视频：
 66     // https://www.bilibili.com/video/BV1Et421L7AY?t=1275.5
 67     cout<<"差分数组为："<<endl;   // 显示差分数组
 68     for (int i = 1; i <= n; i++){
 69         for (int j = 1; j <= m; j++) {
 70             cout<<b[i][j]<<" ";
 71         }
 72         cout<<endl;
 73         
 74     }
 75     cout<<endl;
 76     
 77     while (q--) {
 78         int x1, y1, x2, y2, c;
 79         cin >> x1 >> y1 >> x2 >> y2 >> c;
 80         insert(x1, y1, x2, y2, c);
 81     }
 82 
 83     cout << endl;
 84 
 85     cout << "最后还原的数组为：" << endl;
 86     // 由二维差分数组可以还原出a数组
 87     for (int i = 1; i <= n; i++) {
 88         for (int j = 1; j <= m; j++) {
 89 //
 90             /*
 91             得到整个更新之后的差分数组b后，下面开始求这个差分数组的前缀和，就能得到更新后的原始数组a
 92             S[i][j] = S[i][j - 1] + S[i - 1][j] - S[i - 1][j - 1] + a[i][j]  这个前缀和公式是已经理解了的，
 93             那么对差分数组求前缀和，就直接可以套用上面的这个公式，
 94             重点理解：别看下面的数组是差分数组b，如果按照这个前缀和的公式进行套用，那么每个单元格求前缀和后
 95             就是更新后的原始数组了。下面这个公式是在一个循环里面的，而且也和前缀和的公式一模一样，
 96             赋值语句右边的b[i][j]是求前缀和之前的元素，左边的b[i][j]是最终的前缀和，由于是在循环里面，
 97             b[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1] 这几个元素其实就是前面循环已经计算好了的前缀和，
 98             只是用的是b这个差分数组名称，容易弄混。实质上跟上述的前缀和数组
 99             S[i][j - 1] + S[i - 1][j] - S[i - 1][j - 1] 这几个元素是一样的意思。
100             */
101             b[i][j] = b[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1] + b[i][j];
102             cout << b[i][j] << " ";
103         }
104         cout << endl;
105     }
106 
107     return 0;
108 }

详见https://www.cnblogs.com/Rogerliu/p/18669587