现在有一个5行5列的原始数组a：
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
我们可以通过下述代码对这个数组a进行初始化：
#include <iostream>using namespace std; const int N = 10;
int n, m, q;
int a[N][N], b[N][N]; int main() {
cin >> n >> m >> q;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
cin >> a[i][j]; // 输入原始数组数据 return 0; } 初始化a数组的同时，其实我们是可以同步初始化这个数组的差分数组b的，参考如下代码： #include <iostream>
using namespace std; const int N = 10;
int n, m, q;
int a[N][N], b[N][N]; // 那么为什么差分数组是通过下面的公式进行计算的？这就是我们这篇文章重点要讨论的 void insert(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;
} int main() {
cin >> n >> m >> q;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
cin >> a[i][j]; // 输入原始数组数据 insert(i, j, i, j, a[i][j]); return 0; }
为什么差分数组是通过insert方法下面的公式进行计算的？这就是我们这篇文章重点要讨论的
初始化上述数组a的同时就可以开始进行下面差分数组b的初始化了，
由于a和b初始化数据都是0，因此，原始数组a在通过 cin >> a[i][j]; 手工输入值之前，a的差分数组初始化的时候就是b数组，
上述输入a[i][j]的值以后，就相当于对a[i][j]这一个单元格进行增量更新操作，这种增量更新操作
可以通过差分数组b来完成，也就是相当于对区域 b(i,j)到b(i,j)同时增加一个 a[i][j]
下面调用insert方法时，需要在原始数组里更新的起止两个单元格的坐标一样，也就是x1=x2,y1=y2，
就相当于对本单元格进行批量更新操作，那么insert方法按照差分数组此时的修改规则来修改四个单元格里的值了
这里的理解重点是：1. 初始化时，由于所有元素都是0，b数组就已经是a数组的差分数组了；
2. a数组每个单元格进行手工输入初始化时(上述cin >> a[i][j])，就相当于对每个单元格进行更新操作；
3. insert方法就是按照差分数组的更新公式对四个单元格进行更新。
见下图分析，现在想对原始数组里2行2列到4行4列进行输入数据1的操作
为什么要对差分数组b的上述四个红色字体的单元格做上述操作？
b数组是a数组的差分数组，那么a数组就是b数组的前缀和数组，现在a[2][2]更新为1，那么也就意味着数组b[2][2]也必须更新为1，这样才能保证
b[1][1]到b[2][2]这四个单元格的前缀和为1，而这个前缀和1也必须填到a数组的[2][2]号格上，也就是a数组此时[2][2]号格上输入的1。
PS：为什么a[2][2]上输入了1，b[2][2]上也必须输入1，这是最难理解的地方，其实核心思想就是b是a的差分，那么a就是b的前缀和。
目前前缀和a[2][2]为1，那么也就意味着b数组的b[1][1]至b[2][2]这四个单元格加起来为1，因此只有b[2][2]上填1才能：
(1) 保证前缀和为1；(2)保证a[2][2]为1，因为如果是 b[1][1]填1，那么前缀和a[1][1]就为1；
现在我们来讨论上图中间一部分为什么a[2][2]填入1后，差分数组需要对 b[2][2]+1, b[2][5]-1, b[5][2]-1, b[5][5]+1
(1) 首先a[2][2]更新为1后，按照前面PS部分的说法，必须要在差分数组b[2][2]上更新为1，下面的重点来了：
b[2][2]更新为1后，既然它是差分数组，那么它的前缀和数组如下单元格会受到影响：
上述还只是罗列了两个受影响的单元格a[2][3]和a[3][2]，其实受影响的单元格是如下部分：
这一步一定要能理解！
因为数组a是差分数组b求前缀和得到，因此如果在b[2][2]添加了一个1，那么通过求前缀和，导致
a数组中[2][2]到[5]5]里的单元格都是求前缀和得到的，因此都会加1。然而，这不是我们要的，因为我们目前只想对a[2][2]进行更新1的操作，因此为了让其他
单元格都不受影响，我们会在差分数组b的如下单元格加个 -1，
只要在差分数组b中上述两个单元格加入-1，那么再求前缀和的时候，a数组就变为了：
我们发现，还有三个单元格不为0，也不是我们要的，它们是a[3][3]，a[4][4]，a[5][5]，为了抵消这里的影响，我们可以再次做如下操作，将b[3][3]更新为1即可，即：
至此，我们在a[2][2]上更新了一个1，差分数组b需要做的操作如下：
b[2][2] + 1;b[2][3] - 1;
b[3][2] - 1;
b[3][3] + 1; 反过来说，只有差分数组b做了上述四个操作，才能通过求前缀和得到a数组中只有a[2][2]跟新为1了。 综上所述，其他单元格都按照上述这个公式来操作，那么a数组进行区域更新时，差分数组b所做的操作也是一样的，例如下图：
此时a数组进行a[2][2]到a[4][4]这个区域范围内的更新操作，都加1，只需要将差分数组的红色字部分的单元格进行操作即可。
因此，差分数组每个单元格里的数据是如何来的，就是下面的公式了：
void insert(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;
}
标签：计算,int,单元格,差分,二维,更新,数组,前缀 From： https://www.cnblogs.com/Rogerliu/p/18669587