Acwing798. 差分矩陣

輸入一個 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

輸入樣例：

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
           

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e3 + 10;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}
int main()
{
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            insert(i, j, i, j, a[i][j]);      //建構差分數組
        }
    }
    while (q--)
    {
        int x1, y1, x2, y2, c;
        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++)
        {
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];  //二維字首和
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            printf("%d ", b[i][j]);
        }
        printf("\n");
    }
    return 0;
}
           

如果擴充到二維，我們需要讓二維數組被選中的子矩陣中的每個元素的值加上c,是否也可以達到O(1)的時間複雜度。答案是可以的，考慮二維差分。

a[][]數組是b[][]數組的字首和數組，那麼b[][]是a[][]的差分數組

原數組： a[i][j]

我們去構造差分數組： b[i][j]

使得a數組中a[i][j]是b數組左上角(1,1)到右下角(i,j)所包圍矩形元素的和。

如何構造b數組呢？

我們去逆向思考。

同一維差分，我們構造二維差分數組目的是為了 讓原二維數組a中所選中子矩陣中的每一個元素加上c的操作，可以由O(n*n)的時間複雜度優化成O(1)

已知原數組a中被選中的子矩陣為 以(x1,y1)為左上角，以(x2,y2)為右下角所圍成的矩形區域;

始終要記得，a數組是b數組的字首和數組，比如對b數組的b[i][j]的修改，會影響到a數組中從a[i][j]及往後的每一個數。

假定我們已經構造好了b數組，類比一維差分，我們執行以下操作

來使被選中的子矩陣中的每個元素的值加上c

b[x1][y1] + = c;

b[x1,][y2+1] - = c;

b[x2+1][y1] - = c;

b[x2+1][y2+1] + = c;

每次對b數組執行以上操作，等價于：

for(int i=x1;i<=x2;i++)
  for(int j=y1;j<=y2;j++)
    a[i][j]+=c;