算法刷题笔记 差分矩阵（C++实现）

题目前言

这道题是一道差分算法的拓展题型，是算法刷题笔记到目前为止我认为最困难的题目之一。因此，这篇题解博客的过程记录也最为详细，希望能够为你带来帮助。

题目描述

• 输入一个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

解题思路和代码实现

完整的C++解题代码如下所示：

#include <cstdio>

const int N(1010);
int matrix[N][N];
int dif_matrix[N][N]; // C++中整数类型的二维数组中的所有元素都会被初始化为0

//用于逐步构建差分矩阵的函数
inline void insert_to_matrix(const int& x1, const int& y1, const int& x2, const int& y2, const int& c)
{
    dif_matrix[x1][y1] += c;
    dif_matrix[x1][y2 + 1] -= c;
    dif_matrix[x2 + 1][y1] -= c;
    dif_matrix[x2 + 1][y2 + 1] += c;
}

int main(void)
{
    // 变量定义
    int n, m, q;
    // 变量输入
    scanf("%d %d %d", &n, &m, &q);
    // 根据输入构造差分矩阵（行列下标都从1开始，更加方便）
    for(int i(1); i <= n; ++i)
    {
        for(int j(1); j <= m; ++j)
        {
            int x;
            scanf("%d", &matrix[i][j]);
            insert_to_matrix(i, j, i, j, matrix[i][j]);
        }
    }
    // 构造差分矩阵
    for(int i(0); i < q; ++i)
    {
        int x1, y1, x2, y2, c;
        scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &c);
        insert_to_matrix(x1, y1, x2, y2, c);
    }
    // 差分矩阵构造完成，根据差分矩阵递推出原矩阵并输出
    for(int i(1); i <= n; ++i)
    {
        for(int j(1); j <= m; ++j)
        {
            dif_matrix[i][j] += (dif_matrix[i - 1][j] + dif_matrix[i][j - 1] - dif_matrix[i - 1][j - 1]);
            printf("%d ", dif_matrix[i][j]);
        }
        printf("\n");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

下面将对代码进行逐部分讲解。

第一部分：

#include <cstdio>

const int N(1010);
int matrix[N][N];
int dif_matrix[N][N]; // C++中整数类型的二维数组中的所有元素都会被初始化为0
1
2
3
4
5

• 首先，代码中导入了头文件cstdio，因为需要使用其中的scanf函数和printf函数分别进行变量的输入和结果的输出。之所以使用这两个C语言中的输入输出函数而不是C++中的cin和cout对象，是因为本题中的输入输出都涉及矩阵，数据量较大，使用这两个函数的效率远高于使用cin和cout。
• 定义了大小为1010的整数常量，这是因为根据题目中的数据范围，矩阵的行和列都不会超过1000，而为了防止编程过程中二维数组的访问越界，用一个比1000稍大的数字更好，此处选用1010，用于表示二维数组的最大行数和列数。这个二维数组在所有函数之外进行声明和创建，因此是一个静态数组。静态数组中所有元素都会被默认初始化为0，这就方便了我们后续对该数组的使用。
• 这里的matrix是指原始矩阵，即用户输入的值构成的矩阵；dif_matrix即为差分矩阵。

第二部分

int main(void)
{
    // 变量定义
    int n, m, q;
    // 变量输入
    scanf("%d %d %d", &n, &m, &q);
    // 根据输入构造差分矩阵（行列下标都从1开始，更加方便）
    for(int i(1); i <= n; ++i)
    {
        for(int j(1); j <= m; ++j)
        {
            int x;
            scanf("%d", &matrix[i][j]);
            insert_to_matrix(i, j, i, j, matrix[i][j]);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 这一部分首先使用比cin效率更高的scanf函数读入三个变量，然后根据用户的输入给二维数组中的指定位置插入元素，创建一个模拟的矩阵。
• 需要注意的是，此处我们没有将数组的下标从0开始使用，而是从1开始使用，这是因为用户在后续查询过程中都是输入的数组的行号和列号，两者都不为零，此处将下标从1开始便于和后面的过程保持一致。
• 用户每使用scanf函数输入一个矩阵元素，程序都会使用insert_to_matrix函数来根据该元素的值修改差分矩阵中的内容（起初差分矩阵中的值都是0），这个函数的详细解释请看下面的第三部分。此处将插入的坐标设置为一个单元格。
• 执行完这一部分后，就得到了和原始矩阵相对应的差分矩阵。所以可以看出，并没有一个直接的函数，将原始矩阵转换为差分矩阵，差分矩阵是根据原矩阵和差分矩阵中对应位置的元素之间的关系来一步一步构造的。

第三部分

//用于逐步构建差分矩阵的函数
inline void insert_to_matrix(const int& x1, const int& y1, const int& x2, const int& y2, const int& c)
{
    dif_matrix[x1][y1] += c;
    dif_matrix[x1][y2 + 1] -= c;
    dif_matrix[x2 + 1][y1] -= c;
    dif_matrix[x2 + 1][y2 + 1] += c;
}
1
2
3
4
5
6
7
8

• 将该函数定义为内联函数，是因为函数中不包含循环和复杂的分支语句，并且函数操作量很少，所以定义为inline内联函数有可能可以提高执行效率。
• 函数参数列表使用常引用进行传参，也有可能提高传参效率。
• 该函数用于修改差分矩阵中的值，使得指定的子矩阵中的元素都能满足加上一个常数c，即传入的最后一个参数。具体的公式推导略，可以通过简答的画图理解公式的内容。

第四部分

// 构造差分矩阵
    for(int i(0); i < q; ++i)
    {
        int x1, y1, x2, y2, c;
        scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &c);
        insert_to_matrix(x1, y1, x2, y2, c);
    }
1
2
3
4
5
6
7

• 这一部分根据用户的指定将原始矩阵中的多个子矩阵统一增加一个值，可以通过前面第三部分的函数修改差分矩阵中的四个值进行实现。这样，只需要修改四个值即完成一次修改，而不需要通过双重循环的方式，逐个给子矩阵中的元素加上一个值。

第五部分

// 差分矩阵构造完成，根据差分矩阵递推出原矩阵并输出
    for(int i(1); i <= n; ++i)
    {
        for(int j(1); j <= m; ++j)
        {
            dif_matrix[i][j] += (dif_matrix[i - 1][j] + dif_matrix[i][j - 1] - dif_matrix[i - 1][j - 1]);
            printf("%d ", dif_matrix[i][j]);
        }
        printf("\n");
    }
1
2
3
4
5
6
7
8
9
10

• 根据差分矩阵中的值，只需要一步公式运算即可确定修改后的原始矩阵中的值，公式如上，推导过程可以参考 算法刷题笔记 子矩阵的和（C++实现）。
• 每输出一行矩阵元素都要记得换一行，即输出一个换行符\n。