转载自

leetcode周赛第四题需要用到二维差分,所以就找了篇文章,便于查看

一维差分

定义

$a=[0,1,2,3,4,5]$

$b=[0,1,1,1,1,1]$

为啥呢？

$a[5]?a[4]=b[5]$

$a[4]?a[3]=b[4]$

$a[3]?a[2]=b[3]$

$a[2]?a[1]=b[2]$

$a[1]?a[0]=b[1]$

a数组是b数组的一维前缀和数组

小结

• a数组中，每个数字后面减前面得到的数字填入b数组，b数组就叫a数组的差分数组。
• 同时，a数组就是b数组的前缀和数组。
• 通过“叠加”差分数组，就可以还原出“原数组”的每一个数字！
• 前缀和与差分互为逆运算，有原数组可以计算出差分数组；有差分数组，也可以还原成原数组。

使用场景

在某个区间[l,r]的多次操作都加上（或减去）一个数x时，一维差分可以大大提高运算速度。

举个栗子：

总结公式：

void insert(int l,int r,int c){
    b[l]+=c;
    b[r+1]-=c;
}

我们利用刚才的结论:通过“叠加”差分数组，就可以还原出“原数组”的每一个数字！!这玩意就整一回合适吗？不合适，还不够费功夫的呢！生成一维差分也就算了，从一维差分数组还原回原数组就需要n次运算，整不好还赔了呢！但如果是多次区间加减运算，就合适了！

二维差分

我们有一个矩阵，如下图所示。

根据二维前缀和表示的是左上角矩形的和，由于差分只涉及前面相邻的数（由一维可以推出），并且由前面范围的数相加得到这个位置的数。那么类比二维前缀和和一维差分，可以简单推测出
二维差分的公式

如何从差分矩阵得到原矩阵呢？[就是二维前缀和公式]

举个栗子
比如，我们有一个矩阵 a，如下所示：

1 2 4 3
5 1 2 4
6 3 5 9

那么对应的二维差分矩阵 b 如下：

1  1  2 -1
4 -5 -1  3
1  1  1  2

二维差分用途

和一维差分的用途基本一致，在一个二维矩阵中，有多块区间需要增加或减少一个数值，多次操作后求最终的矩阵内容。如果按照传统办法，就是二层循环，复杂度很高，如果预处理出一个二维的差分矩阵，以后的多轮操作都转为了4次加加减减操作，可以视为O(1)级别的时间复杂度，运算效率将得到极大提高。

二维差分构建

如果我们要在左上角是 (x1,y1)，右下角是 (x2,y2) 的矩形区间每个值都 +c，如下图所示

在我们要的区间开始位置（x1,y1）处 +c，根据前缀和的性质，那么它影响的就是整个黄色部分，多影响了两个蓝色部分，所以在两个蓝色部分 -c 消除 +c 的影响，而两个蓝色部分重叠的绿色部分多了个 -c 的影响，所以绿色部分 +c 消除影响。所以对应的计算方法如下：

void insert(int x1, int y1, int x2, int y2, int c){
    b[x1][y1] += c;             //开始位置增加C
    b[x2 + 1][y1] -= c;         //见上面的图，把第二行的蓝色区域减去C
    b[x1][y2 + 1] -= c;         //见上面的图，把第一行的蓝色区域减去C
    b[x2 + 1][y2 + 1] += c;     //交叉位置被减了两次，需要补回来。
}