【数据结构】二维差分数组

题目链接 

【模板】二维差分_牛客题霸_牛客网

牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推，求职就业一站解决_牛客网

描述

给定一个 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)))