題目前言

這道題是一道差分算法的拓展題型，是算法刷題筆記到目前為止我認為最困難的題目之一。因此，這篇題解博客的過程記錄也最為詳細，希望能夠為你帶來幫助。

題目描述

• 輸入一個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");}
}

下面將對代碼進行逐部分講解。

第一部分：

#include <cstdio>const int N(1010);
int matrix[N][N];
int dif_matrix[N][N]; // C++中整數類型的二維數組中的所有元素都會被初始化為0

• 首先，代碼中導入了頭文件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]);}}

• 這一部分首先使用比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;
}

• 將該函數定義為內聯函數，是因為函數中不包含循環和復雜的分支語句，并且函數操作量很少，所以定義為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);}

• 這一部分根據用戶的指定將原始矩陣中的多個子矩陣統一增加一個值，可以通過前面第三部分的函數修改差分矩陣中的四個值進行實現。這樣，只需要修改四個值即完成一次修改，而不需要通過雙重循環的方式，逐個給子矩陣中的元素加上一個值。

第五部分

// 差分矩陣構造完成，根據差分矩陣遞推出原矩陣并輸出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");}

• 根據差分矩陣中的值，只需要一步公式運算即可確定修改后的原始矩陣中的值，公式如上，推導過程可以參考 算法刷題筆記 子矩陣的和（C++實現）。
• 每輸出一行矩陣元素都要記得換一行，即輸出一個換行符\n。