目录

复习：

二维差分数组：

引入：

 标记数组：

求前缀和：

参考代码：

---

复习：

在学习二维差分之前，我们先复习一下一维差分

给定一个数组

int arr[5]={1,2,3,4,5};

要对这个数组差分，也就是对这个数组的l到r个元素同时操作（加减），比如对这个数组的下标1到3的元素都进行+2操作

但这种操作太过于繁琐，于是可以用到一维前缀和

先创建一个比原数组大一个的标记数组

在当前位置起始位置+2，并在末尾位置的下一个-2

再把求出标记数组的前缀和，就变成了

此时sumarr+arr的值就是差分后的结果了

二维差分数组：

引入：

（这里我就默认大家都学过二维前缀和了）

顾名思义，是二维数组中一个矩阵的差分，给定一个二维数组

int arr[4][4]={ 1, 2, 3, 4,
                5, 6, 7, 8,
                9,10,11,12,
                3,14,15,16};

想让arr[1][1]到arr[2][2]的值都加上2，怎么用差分做呢？

和一维差分一样，我们可以定义一个比原数组大一个的标记数组（大一个是为了后面减的时候不会越界）

 按照一维差分的思维，我们可以在增加2的起点+2，但这样的话就会导致从起点开始到结尾的矩阵都会+2，所以需要再在增加2的矩阵末尾-2

但要想给二维数组中的一个矩阵-2，需要操作两次，这两个点都会影响后面的数

但这样的话就有一部分区域执行了两次-2，所以要把这部分区域再+2

如图，红色区域是我们想要给它+2的区域，绿色部分是-2操作会波及到的区域，粉色部分是重复-2的区域 ，所以需要在给它+2，求出标记数组的前缀和，就变成了

再把sumarr和arr相加，得到的结果就是差分后的结果

 标记数组：

定义x1,y1,x2,y2,k，表示将arr数组中的arr[x1][y1]到arr[x2][y2]增加k个值

首先给从(x1,y1)到数组最后的矩阵+k

d[x1][y1]+=k;

由于(x2,y2)后面的区域也被加了，所以我们现在需要减去

首先减去这块区域，也就是(x2+1,y1)以及以后的区域-k

d[x2+1][y1]-=k;

然后减去另一块区域，也就是从(x1,y2+1)以及以后的区域-k

d[x1][y2+1]-=k;

这样之后我们发现绿色部分有一块区域重叠了，被减了两次k，所以我们需要给这块区域再加一次k

也就是(x2+1,y2+1)以及以后的区域+k

d[x2+1][y2+1]+=k;

求前缀和：

再把这个标记数组求出前缀和来，最后就只有棕色区域被+k，其余是0

参考代码： 

int sum[4][4]={0};
    for(i=0;i<4;i++)
        for(j=0;j<4;j++)
        {
            if(i==0 && j==0)
                sum[0][0]=d[0][0];
            else if(i==0)
                sum[0][j]=sum[0][j-1]+d[0][j];
            else if(j==0)
                sum[i][0]=sum[i-1][0]+d[i][0];
            else
                sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+d[i][j];
        }

 再把这个前缀和数组加到原数组中，就可以得到最终的值

 for(i=0;i<3;i++)
        for(j=0;j<3;j++)
            arr[i][j]+=sum[i][j];

参考代码：

#include <stdio.h>
int main()
{
    int arr[4][4]={ 1, 2, 3, 4,      //1 3 6
                    5, 6, 7, 8,      //5 12 21
                    9,10,11,12,
                   13,14,15,16};     //12 27 45
    int d[5][5]={0};
    int i,j;
    int x1,y1,x2,y2,k;
    scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&k);
    //标记区域
    d[x1][y1]+=k;
    d[x1][y2+1]-=k;
    d[x2+1][y1]-=k;
    d[x2+1][y2+1]+=k;
    //标记区域的前缀和
    int sum[4][4]={0};
    for(i=0;i<4;i++)
        for(j=0;j<4;j++)
        {
            if(i==0 && j==0)
                sum[0][0]=d[0][0];
            else if(i==0)
                sum[0][j]=sum[0][j-1]+d[0][j];
            else if(j==0)
                sum[i][0]=sum[i-1][0]+d[i][0];
            else
                sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+d[i][j];
        }
    //整合
    for(i=0;i<3;i++)
        for(j=0;j<3;j++)
            arr[i][j]+=sum[i][j];
    return 0;
}