矩阵加法时间复杂度优化咨询：如何将O(N³)降至更低？

核心思路：二维差分法 #

原方案每次更新都遍历矩形内所有元素，最坏情况下时间复杂度达到O(N³)。我们可以通过二维差分矩阵将单次区间更新的操作复杂度降至O(1)，最后通过两次前缀和计算得到所有元素的总增量，整体时间复杂度优化到O(N²)。

具体步骤 #

假设原矩阵为A[N][N]，我们额外维护一个(N+2)×(N+2)的差分矩阵diff（多开两行两列是为了避免边界越界判断），初始值全为0。

1. 处理每一次更新操作 #

对每一组输入的R1, R2, C1, C2, V，只需修改diff的4个位置：

diff[R1][C1] += V
diff[R1][C2 + 1] -= V
diff[R2 + 1][C1] -= V
diff[R2 + 1][C2 + 1] += V

这四个操作的作用是标记矩形区域的增量起始与结束边界，后续前缀和会自动将增量扩散到整个目标矩形范围。

2. 计算前缀和得到总增量矩阵 #

完成所有更新后，对diff矩阵执行两次前缀和计算：

• 行方向前缀和：遍历每一行，从左到右累加

  for i from 1 to N:
      for j from 2 to N:
          diff[i][j] += diff[i][j-1]
  

• 列方向前缀和：遍历每一列，从上到下累加

  for j from 1 to N:
      for i from 2 to N:
          diff[i][j] += diff[i-1][j]
  

  此时diff[i][j]就是原矩阵A[i][j]需要累加的总增量。

3. 生成最终矩阵并输出 #

将原矩阵与增量矩阵相加，得到最终结果并输出：

for i from 1 to N:
    for j from 1 to N:
        A[i][j] += diff[i][j]
        print(A[i][j])

时间复杂度分析 #

• 更新操作：N次更新，每次O(1)，总耗时O(N)
• 前缀和计算：两次O(N²)级别的遍历，总耗时O(N²)
• 最终矩阵生成：O(N²)级别的遍历

整体时间复杂度为O(N²)，远低于原方案的O(N³)。

示例验证 #

以N=3，输入更新参数R1=1, R2=2, C1=1, C2=2, V=5为例：

1. 修改diff矩阵后，关键位置的值为：

   diff[1][1] = 5, diff[1][3] = -5
   diff[3][1] = -5, diff[3][3] = 5
   

2. 行前缀和后：

   第一行：5, 5, 0
   第二行：0, 0, 0
   第三行：-5, -5, 0
   

3. 列前缀和后：

   第一列：5, 5, 0
   第二列：5, 5, 0
   第三列：0, 0, 0
   

   结果完全符合预期：1-2行、1-2列的元素都累加了5。

内容的提问来源于stack exchange，提问作者JourneyToUngoro