C++题解 差分矩阵

题目描述

输入一个 nn 行 mm 列的整数矩阵，再输入 qq 个操作，每个操作包含五个整数 $x_1,y_1,x_2,y_2,c$ ，其中 $(x_1,y_1) 和 (x_2,y_2)$ 表示一个子矩阵的左上角坐标和右下角坐标。

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

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

输入格式

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

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

接下来 $q$ 行，每行包含 $5$ 个整数 $x_1,y_1,x_2,y_2,c$，表示一个操作。

输出格式

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

数据范围

$$
1≤n,m≤1000\
1≤q≤100000\
1≤x_1≤x_2≤n\
1≤y_1≤y_2≤m\
−1000≤c≤1000\
−1000≤矩阵内元素的值≤1000\
$$

输入样例：

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

输出样例：

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

思想

差分是前缀和的逆运算，通过差分，我们可以实现O（1）的，对矩阵指定区间进行加减操作

差分数组：

首先给定一个原矩阵a：a[1][q], a[1][2], a[1][3],,,,,, a[n][n];

然后我们构造一个矩阵b ： b[1][1] ,b[1][2] , b[1][3],,,,,, b[n][n];

使得 a[i][i] = b[1][1] + b[1][2]+ b[1][3] +,,,,,, + b[i][i]

也就是说，a矩阵是b矩阵的前缀和矩阵，反过来我们把b矩阵叫做a矩阵的差分矩阵。换句话说，每一个a[i][i]都是b矩阵中从头开始的一段矩阵和。

如何构造差分矩阵

我们假定原矩阵a全为0，给原矩阵a赋初始值的过程视为 对原矩阵a进行 单位为1的加减操作

例子

我要对a矩阵的【l,r】进行加add操作，则我对差分矩阵b进行如下操作

	b[x1][y1] += add;
    b[x2 + 1][y1] -= add;
    b[x1][y2 + 1] -= add;
    b[x2 + 1][y2 + 1] += add;

此处借用[@z林深时见鹿]的图

b[x1][ y1 ] +=c; 对应图1 ,让整个a数组中蓝色矩形面积的元素都加上了c。
b[x1,][y2+1]-=c ; 对应图2 ,让整个a数组中绿色矩形面积的元素再减去c，使其内元素不发生改变。
b[x2+1][y1]- =c ; 对应图3 ,让整个a数组中紫色矩形面积的元素再减去c，使其内元素不发生改变。
b[x2+1][y2+1]+=c; 对应图4,,让整个a数组中红色矩形面积的元素再加上c，红色内的相当于被减了两次，再加上一次c，才能使其恢复。

矩阵和计算

$S[i,j]$即为图1红框中所有数的的和为：
$S[i,j]=S[i,j−1]+S[i−1,j]−S[i−1,j−1]+a[i,j]$

以下是代码实现

//
// Created by Owwkmidream on 2021/10/30.
//
#include "iostream"

using namespace std;

const int N = 1010;

int a[N][N], b[N][N];

void insert(int x1, int y1, int x2, int y2, int add)
{
    b[x1][y1] += add;
    b[x2 + 1][y1] -= add;
    b[x1][y2 + 1] -= add;
    b[x2 + 1][y2 + 1] += add;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n,m,q;
    cin >> n >> m >> q;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int tmp;
            cin >> tmp;
            insert(i ,j, i, j, tmp);
        }
    }

    int x1, x2, y1, y2, c;
    while (q -- ) {
        cin >> 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) {
            a[i][j] = a[i][j-1] + a[i-1][j] - a[i-1][j-1] + b[i][j];
            cout << a[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}