二维差分

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

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