題目鏈接?

【模板】二維差分_牛客題霸_牛客網

牛客網 - 找工作神器|筆試題庫|面試經驗|實習招聘內推，求職就業一站解決_牛客網

描述

給定一個?n×mn×m?的整數矩陣?bb，矩陣的下標從?11?開始記作?bi,jbi,j?。現在需要支持?qq?次操作，第?tt?次操作給定五個整數?x1,y1,x2,y2,kx1?,y1?,x2?,y2?,k，表示將以左上角?(x1,y1)(x1?,y1?)、右下角?(x2,y2)(x2?,y2?)?為邊界的子矩陣內的每個元素都增加?kk。全部操作執行完畢后，請輸出最終矩陣。

【名詞解釋】
???子矩陣：從矩陣中連續選取若干行與若干列得到的矩形區域。

輸入描述：

在一行上輸入三個整數?n,m,q(1≦n,m≦1000;?1≦q≦105)n,m,q(1≦n,m≦1000;?1≦q≦105)，依次表示矩陣行數、列數與操作次數。
此后?nn?行，第?ii?行輸入?mm?個整數?bi,1,bi,2,…,bi,m(?109≦bi,j≦109)bi,1?,bi,2?,…,bi,m?(?109≦bi,j?≦109)，描述矩陣初始元素。
再之后?qq?行，每行輸入五個整數?x1,y1,x2,y2,k(1≦x1≦x2≦n;?1≦y1≦y2≦m;??109≦k≦109)x1?,y1?,x2?,y2?,k(1≦x1?≦x2?≦n;?1≦y1?≦y2?≦m;??109≦k≦109)，描述一次矩陣加法操作。

輸出描述：

輸出?nn?行，每行?mm?個整數，表示所有操作結束后矩陣的最終狀態。同行相鄰元素之間使用一個空格分隔。

示例：?2 3 4
1 2 3
4 5 6
1 1 2 2 3
1 2 2 3 -1
1 1 1 3 4
1 1 2 1 1輸出 ;9 8 6
8 7 5

說明：

在該樣例中： 
???第一次操作將 (1,1)?(2,2)(1,1)?(2,2) 內的四個元素各自增加 3； 
???第二次操作將 (1,2)?(2,3)(1,2)?(2,3) 內的六個元素各自減少 1； 
???第三次操作將 (1,1)?(1,3)(1,1)?(1,3) 內的三個元素各自增加 4； 
???第四次操作將 (1,1)?(2,1)(1,1)?(2,1) 內的兩個元素各自增加 1。 
最終得到的矩陣如輸出所示。

示例2：?

示例2
輸入：
3 3 1
0 0 0
0 0 0
0 0 0
1 1 3 3 5
復制
輸出：
5 5 5
5 5 5
5 5 5
復制
說明：
該樣例中只進行一次操作，將整個矩陣所有元素都增加 
5
5

這個問題是典型的二維區間更新問題，解題的關鍵在于高效處理多次子矩陣的增量更新操作。傳統方法是每次操作遍歷整個子矩陣并逐一更新，時間復雜度為 O (nmq)，當 n、m、q 很大時會導致超時。這里使用的二維差分技術能將單次操作的時間復雜度優化到 O (1)，整體復雜度降為 O (n*m + q)。

核心思路

1. 差分矩陣：
   差分矩陣?d[i][j]?記錄原矩陣?matrix?中每個位置的增量變化。通過差分矩陣，可以快速對整個子矩陣進行更新，而無需遍歷每個元素。

2. 初始化差分矩陣：
   根據原矩陣?matrix?構建差分矩陣?d，使得通過前綴和運算可以還原出原矩陣。具體公式為：

   
   d 坐標從 1 開始 使用 1-base 坐標
   matrix[][]  坐標從0開始   使用0-base 坐標
   d[i][j]=matrix[i][j] -matrix[i-1][j]-matrxi[i][j-1] +matrix[i-1][j-1]

? ?3 .? ? ?區間更新優化：
? ?每次對子矩陣?(x1, y1)?到?(x2, y2)?增加?k?時，只需修改差分矩陣的四個角點：

#  d 坐標從 1 開始 使用 1-base 坐標
d[x1][y1]  +=k   # 左上角 ，增量開始
d[x2+1][y1]-=k  #   左下角 ，增量結束 列結束
d[x1][y2+1] -=k  # 右上角，增量結束， 行方向

這樣每次操作的時間復雜度僅為 O (1)。

結果還原： 所有操作完成后，通過前綴和運算將差分矩陣還原為最終的矩陣：

matrix[i][j]=d[i][j]+matrix[i-1][j]+matrix[i][j-1]-matrix[i-1][j-1]#  matrix[i-1][j-1]  為matrix[i-1][j]+matrix[i][j-1]公共部分加了兩次

?關鍵步驟?差分矩陣初始化：

d=[ [ 0 for _ in range(m+2)  ]  for _ in range(n+2) ]for i in range(1,n+1):for j in range(1,m+1):d[i][j]=matrix[i-1][j-1]if  i> 1:d[i][j]-=matrix[i-2][j-1]if j>1:d[i][j]-=matrix[i-1][j-2]if i> 1 and j>1 :d[i][j]+=matrix[i-2][j-2]  # 公共部分上面減去兩次 ，加回來

? 4. 處理區間優化

??

 for i  in  range(q):x1,y1,x2,y2,k=map(int,input().split())d[x1][y1]+=k # 開始左上角d[x2+1][y1]-=k # 結束左下角 行結束d[x2][y2+1] -=k  # 結束 右上角  列結束d[x2+1][y2+1]+=1  #公共區域減去兩次 加回來

5.? 還原最終矩陣

??

for i in range(1,n+1):for j in  range(1,m+1):matrix[i-1][j-1]=d[i][j]if i>1:matrix[i-1][j-1]-=dp[i-2][j-1]if j >1:matrix[i-1][j-1]-=dp[i-1][j-2]if i>1  and  j>1:matrix[i-1][j-1]-=dp[i-2][j-1]

復雜度分析

• 時間復雜度：初始化 O (nm) + 更新操作 O (q) + 還原 O (nm) = O(n*m + q)
• 空間復雜度：O (n*m)（存儲差分矩陣）

這種方法在處理大量區間更新時非常高效，適用于題目中的數據范圍（n, m ≤ 1000，q ≤ 10^5）。

案例

二維差分矩陣的構建原理，我們通過一個具體例子來理解它的推導過程。

例子：3×3 矩陣

假設原矩陣?matrix?如下：

matrix = [[1, 2, 3],[4, 5, 6],[7, 8, 9]
]

步驟 1：明確差分矩陣的定義

差分矩陣?d[i][j]?記錄的是原矩陣?matrix?中每個位置的增量變化，使得通過前綴和運算可以還原出原矩陣。具體來說：

• 前綴和公式：
  matrix[i][j] = 左上角到(i,j)的所有d值之和
  即：

  python

  運行

  matrix[i][j] = d[1][1] + d[1][2] + ... + d[i][j]
  

步驟 2：推導差分矩陣的遞推關系

為了滿足前綴和公式，差分矩陣?d[i][j]?應滿足：

d[i][j] = matrix[i][j] - 上方區域的和 - 左方區域的和 + 左上角重疊區域的和

數學推導：

python

運行

d[i][j] = matrix[i][j] - (matrix[i-1][j]) - (matrix[i][j-1]) + (matrix[i-1][j-1])

這里加上?matrix[i-1][j-1]?是因為左上角區域被重復減去了兩次。

手動計算差分矩陣

我們來手動計算上面例子的差分矩陣?d：

初始化差分矩陣

python

運行

d = [[0, 0, 0, 0],  # 第0行（索引0）和第0列（索引0）為輔助行/列[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0]
]

計算 d [1][1]

python

運行

d[1][1] = matrix[0][0] = 1

計算 d [1][2]

python

運行

d[1][2] = matrix[0][1] - matrix[0][0] = 2 - 1 = 1

計算 d [2][1]

python

運行

d[2][1] = matrix[1][0] - matrix[0][0] = 4 - 1 = 3

計算 d [2][2]

python

運行

d[2][2] = matrix[1][1] - matrix[0][1] - matrix[1][0] + matrix[0][0]= 5 - 2 - 4 + 1= 0

完整差分矩陣

plaintext

d = [[0, 0, 0, 0],[0, 1, 1, 1],[0, 3, 0, 0],[0, 3, 0, 0]
]

驗證前綴和還原

通過差分矩陣?d?的前綴和運算，驗證能否還原出原矩陣?matrix：

還原 matrix [1][1]

matrix[1][1] = d[1][1] + d[1][2] + d[2][1] + d[2][2]= 1 + 1 + 3 + 0= 5  # 正確

還原 matrix [2][2]

matrix[2][2] = d[1][1] + d[1][2] + d[1][3] + d[2][1] + d[2][2] + d[2][3] + d[3][1] + d[3][2] + d[3][3]= 1 + 1 + 1 + 3 + 0 + 0 + 3 + 0 + 0= 9  # 正確

公式總結

二維差分矩陣的核心公式：

d[i][j] = matrix[i][j] - matrix[i-1][j] - matrix[i][j-1] + matrix[i-1][j-1]

這個公式確保了通過前綴和運算可以正確還原原矩陣，從而實現高效的區間更新操作。

疑問? d[i][j] 對應matrix[i-1][j-1]?？?

為什么 d[1][1] = matrix[0][0] = 1 但是按照d[i][j] = matrix[i][j] - (matrix[i-1][j]) - (matrix[i][j-1]) + (matrix[i-1][j-1]) 應該d[i][j]=matrix[1][1]-matrix[0][1]=matrix[1][0]+matrix[0][0] =0

這里的混淆源于索引系統的轉換和邊界條件的處理。

關鍵澄清：索引系統轉換

你的代碼使用了1-based 索引（從 1 開始），而 Python 列表默認是0-based 索引（從 0 開始）。這導致：

• matrix[0][0]?對應原矩陣的第 1 行第 1 列（1-based）
• d[1][1]?對應差分矩陣的第 1 行第 1 列（1-based）

因此，d[1][1]?應直接等于?matrix[0][0]，因為它們表示同一個位置。

公式應用的邊界條件

差分公式?d[i][j] = matrix[i][j] - matrix[i-1][j] - matrix[i][j-1] + matrix[i-1][j-1]?在邊界處需要特殊處理：

當 i=1 或 j=1 時

• matrix[i-1][j]?或?matrix[i][j-1]?可能越界（例如?matrix[-1][j]）
• 此時，越界部分視為?0（因為原矩陣的 "前一行" 或 "前一列" 不存在）

具體例子

對于?d[1][1]（1-based）：

python

運行

i = 1, j = 1  # 對應 matrix[0][0]（0-based）# 代入公式：
d[1][1] = matrix[0][0] - matrix[-1][0] - matrix[0][-1] + matrix[-1][-1]# 由于 matrix[-1][0] 和 matrix[0][-1] 越界，視為 0：
d[1][1] = matrix[0][0] - 0 - 0 + 0 = matrix[0][0] = 1

計算的?d[1][1] = 0?是錯誤的，因為：

1. 索引混淆：你誤用了 1-based 索引代入公式
   • 例如，你寫的?matrix[1][1]?實際對應原矩陣的第 2 行第 2 列（值為 5）
2. 忽略邊界條件：當?i=1?或?j=1?時，公式中的越界項需視為 0

正確計算示例

?3×3 矩陣例子驗證：

原矩陣（0-based）：

matrix = [[1, 2, 3],  # 第0行[4, 5, 6],  # 第1行[7, 8, 9]   # 第2行
]

差分矩陣初始化（1-based）：

d[1][1] = matrix[0][0] = 1  # 邊界情況，直接賦值d[1][2] = matrix[0][1] - matrix[0][0] = 2 - 1 = 1
d[2][1] = matrix[1][0] - matrix[0][0] = 4 - 1 = 3d[2][2] = matrix[1][1] - matrix[0][1] - matrix[1][0] + matrix[0][0]= 5 - 2 - 4 + 1= 0

?完整差分矩陣：

d = [[0, 0, 0, 0],  # 第0行（輔助行）[0, 1, 1, 1],  # 第1行（對應原矩陣第0行）[0, 3, 0, 0],  # 第2行（對應原矩陣第1行）[0, 3, 0, 0]   # 第3行（對應原矩陣第2行）
]

代碼驗證

for i in range(1, n + 1):for j in range(1, m + 1):d[i][j] = matrix[i - 1][j - 1]  # 對應原矩陣的位置if i > 1:  # 處理 i > 1 的情況d[i][j] -= matrix[i - 2][j - 1]if j > 1:  # 處理 j > 1 的情況d[i][j] -= matrix[i - 1][j - 2]if i > 1 and j > 1:  # 處理 i > 1 且 j > 1 的情況d[i][j] += matrix[i - 2][j - 2]

總結

1. 索引轉換：1-based 的?d[i][j]?對應 0-based 的?matrix[i-1][j-1]
2. 邊界條件：當?i=1?或?j=1?時，公式中的越界項視為 0

差分矩陣的初始化確實需要特別注意索引系統的轉換和邊界條件，這是理解二維差分的關鍵

為什么差分矩陣使用 1-based 索引？

差分矩陣?d?的索引從 1 開始，主要是為了避免處理邊界條件時的復雜判斷。具體原因如下：

1. 公式簡潔性
   二維差分的核心公式：

   d[i][j] = matrix[i][j] - matrix[i-1][j] - matrix[i][j-1] + matrix[i-1][j-1]

   如果使用 0-based 索引，當?i=0?或?j=0?時，matrix[i-1][j]?會導致索引越界（如?matrix[-1][j]），需要額外的條件判斷。

2.減少特殊處理
使用 1-based 索引后，d[1][1]?對應?matrix[0][0]，公式在邊界處依然成立。例如：

python

運行

d[1][1] = matrix[0][0] - matrix[-1][0] - matrix[0][-1] + matrix[-1][-1]
# 越界部分視為0，因此 d[1][1] = matrix[0][0]

代碼中的索引對應關系

差分矩陣?d?(1-based)	原矩陣?matrix?(0-based)
d[1][1]	matrix[0][0]
d[1][2]	matrix[0][1]
d[i][j]	matrix[i-1][j-1]

驗證代碼邏輯

讓我們通過你的 3×3 矩陣例子驗證：

原矩陣（0-based）：

matrix = [[1, 2, 3],  # 第0行[4, 5, 6],  # 第1行[7, 8, 9]   # 第2行
]

差分矩陣初始化（1-based）：

d[1][1] = matrix[0][0] = 1  # 邊界情況，直接賦值
d[1][2] = matrix[0][1] - matrix[0][0] = 2 - 1 = 1
d[2][1] = matrix[1][0] - matrix[0][0] = 4 - 1 = 3
d[2][2] = matrix[1][1] - matrix[0][1] - matrix[1][0] + matrix[0][0]= 5 - 2 - 4 + 1 = 0

如果使用 0-based 索引會怎樣？ 如果差分矩陣 d 也使用 0-based 索引，代碼會變得更復雜：

# 假設d也使用0-based索引（這不是你的代碼！）
d = [[0] * m for _ in range(n)]for i in range(n):for j in range(m):d[i][j] = matrix[i][j]if i > 0:d[i][j] -= matrix[i-1][j]if j > 0:d[i][j] -= matrix[i][j-1]if i > 0 and j > 0:d[i][j] += matrix[i-1][j-1]# 更新操作也需要調整
for _ in range(q):x1, y1, x2, y2, k = map(int, input().split())x1 -= 1  # 轉換為0-basedy1 -= 1x2 -= 1y2 -= 1d[x1][y1] += kif x2 + 1 < n:d[x2+1][y1] -= kif y2 + 1 < m:d[x1][y2+1] -= kif x2 + 1 < n and y2 + 1 < m:d[x2+1][y2+1] += k

可以看到，使用 0-based 索引會引入更多邊界判斷，代碼更易出錯。

總結

1. 索引系統差異：

   • matrix?是 Python 列表，使用 0-based 索引
   • d?使用 1-based 索引是為了簡化差分公式的實現

2. 優勢：

   • 避免了?matrix[-1][j]?這種越界情況
   • 差分公式在所有位置統一適用，無需特殊處理邊界

調整差分數組?

    d[x1][y1] += kd[x2 + 1][y1] -= kd[x1][y2 + 1] -= kd[x2 + 1][y2 + 1] += k

這段代碼是二維差分矩陣的區間更新操作核心邏輯，讓我詳細解釋它的工作原理：

二維差分的區間更新原理 當我們要對原矩陣的子矩陣 (x1,y1) 到 (x2,y2) 全部加上 k 時，只需在差分矩陣 d 上修改四個角點：

d[x1][y1] += k 從 (x1,y1) 開始的所有元素都會因為這個點的增量而增加 k。

d[x2+1][y1] -= k 在 x2+1 行的 y1 列處減去 k，抵消掉從 x2+1 行開始的多余增量（因為我們只需要更新到 x2 行）。

d[x1][y2+1] -= k 在 y2+1 列的 x1 行處減去 k，抵消掉從 y2+1 列開始的多余增量（因為我們只需要更新到 y2 列）。

d[x2+1][y2+1] += k 在 (x2+1, y2+1) 處加上 k，抵消掉前兩步重復減去的部分（雙重抵消）。

可視化示例

假設原矩陣是一個全 0 矩陣，我們要對左上角?(1,1)?到右下角?(2,2)?的子矩陣加上?3：

原矩陣:           差分矩陣d:
0 0 0 0           0 0 0 0 0
0 0 0 0           0 3 0 0 -3
0 0 0 0    →      0 0 0 0 0
0 0 0 0           0 0 0 0 00 -3 0 0 3

• d[1][1] +=3：從?(1,1)?開始的區域都會被加上 3
• d[3][1] -=3：從第 3 行開始的區域會被減去 3（抵消）
• d[1][3] -=3：從第 3 列開始的區域會被減去 3（抵消）
• d[3][3] +=3：右下角?(3,3)?處加 3（抵消雙重抵消）

為什么這樣有效？ 差分矩陣的核心思想是：通過前綴和運算還原原矩陣。當我們修改差分數組的某個點時，會影響從該點開始的所有前綴和結果。 通過這四個角點的修改，我們巧妙地控制了增量的作用范圍，使得： 子矩陣內的每個元素都增加 k 子矩陣外的元素不受影響 這種方法將每次區間更新的時間復雜度從 O (n*m) 優化到 O (1)，大大提高了效率。

完整代碼

n ,m , q =map(int ,input().split())
maxtrix = [list(map(int, input().split())) for _ in range(n)]d = [[0 for _ in range(m + 2)] for _ in range(n + 2)]
# 初始化差分數組
for i in range(1, n + 1):for j in range(1, m + 1):d[i][j] = maxtrix[i - 1][j - 1]if i > 1:d[i][j] -= maxtrix[i - 2][j - 1]if j > 1:d[i][j] -= maxtrix[i - 1][j - 2]if i > 1 and j > 1:d[i][j] += maxtrix[i - 2][j - 2]
# 處置修改
for _ in range(q):x1, y1, x2, y2, k = map(int, input().split())# 調整差分d[x1][y1] += kd[x2 + 1][y1] -= kd[x1][y2 + 1] -= kd[x2 + 1][y2 + 1] += k# 根據差分還原數組
for i in range(1, n + 1):for j in range(1, m + 1):maxtrix[i - 1][j - 1] = d[i][j]if i > 1:maxtrix[i - 1][j - 1] += maxtrix[i - 2][j - 1]if j > 1:maxtrix[i - 1][j - 1] += maxtrix[i - 1][j - 2]if i > 1 and j > 1:maxtrix[i - 1][j - 1] -= maxtrix[i - 2][j - 2]for row in maxtrix:print(" ".join(map(str, row)))