SolitudeAlma

今天我们来讲一下二维差分

什么是二维差分呢？

相信了解一维差分的小伙伴都知道，差分和前缀和其实是互逆的。二位前缀和是计算矩阵中的一个点包括其和左上角的所有点的值的和，那么差分的作用就是在时间复杂度是 $O(1)$ 的情况下对一个矩阵操作，比如某区域的点都加上一个数。

那么我们应该怎么构建差分数组呢，其实和一维差分差不多，只不过是多了一维。那么有了一维差分的构建经验对于二位差分我们直接用插入函数即可，原理下面会说。

由一维差分我们可以知道， a[i] 是 b[1]...b[i] 的前缀和，如果我们要对区间 [l , r] 中的数都加上一个数c的话只需要让 b[l] += c 并且 b[r + 1] -= c 即可，这样用差分数组构建新数组时，区间 [l , r] 中的数都会在原基础上加上c。

如果我们把这个区间放缩一下，并且让数组元素都为0的这个数组a作为我们的原数组，那么数组a的差分数组b也是全为0，这样我们就构成了差分数组，那么我们真正需要输入到数组中的数就可以利用二位差分的性质进行了，也就是当区间 l = r时，我们让其加上一个需要输入的数，这样既输入了数据，也构成了差分数组。

我们来看一下对任意子矩阵都加上一个数的话，应该怎么利用差分数组。

从图中我们可以很清楚的看到，如果在x1，y1上加一个数c那么它右下角的数都会加上c，那么该怎么办呢，其实这也是容斥定理。我们只需要减去右边多加的部分和下边多加的部分最后再加上重复减去的部分即可

那么代码该怎么写呢，我们来看看模板吧


给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

其实挺简单的，我们来做一道模板题熟悉一下吧

AcWing 798.差分矩阵

题目描述

输入一个n行m列的整数矩阵，再输入q个操作，每个操作包含五个整数x1, y1, x2, y2, c，其中(x1, y1)和(x2, y2)表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上c。

请你将进行完所有操作后的矩阵输出。

输入格式

第一行包含整数n,m,q。

接下来n行，每行包含m个整数，表示整数矩阵。

接下来q行，每行包含5个整数x1, y1, x2, y2, c，表示一个操作。

输出格式

共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。

数据范围

$1≤n,m≤1000,$
$1≤q≤100000,$
$1≤x1≤x2≤n,$
$1≤y1≤y2≤m,$
$−1000≤c≤1000,$
$−1000≤矩阵内元素的值≤1000$

输入样例：

输出样例：

2 3 4 1
4 3 4 1
2 2 2 2

C++代码


#include <cstdio>

using namespace std;

const int N = 1010;

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()
{
    scanf("%d%d%d" , &n , &m , &q);

    for(int i = 1; i <= n; i ++)
    {
       for(int j = 1; j <= m; j ++)
        {
            scanf("%d" , &a[i][j]);
            insert(i , j , i , j , a[i][j]);
        } 
    }
        
    while(q --)
    {
        int x1 , y1 , x2 , y2 , c;

        scanf("%d%d%d%d%d" , &x1 , &y1 , &x2 , &y2 , &c);

        insert(x1 , y1 , x2 , y2 , c);
    }

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            b[i][j] += b[i - 1][j] + b[i][j -1] - b[i - 1][j - 1];
            printf("%d " , b[i][j]);
        }
        puts("");
    }
    return 0;
}

引用

引用一些大佬的题解

p_c AcWing 798. 差分矩阵

dongwa_zzuli AcWing 798. 差分矩阵_java

vanilla AcWing 798. 差分矩阵

二维差分