如何将N*N矩阵子矩阵加法的O(N³)时间复杂度优化至更低？

问题背景 #

现有一个N×N的矩阵M，初始值为随机数。需要执行N次循环，每次输入参数Row1、Row2、Col1、Col2、Value，对指定子矩阵内的所有元素累加Value。原实现采用三层嵌套循环遍历子矩阵元素，时间复杂度为O(N³)，需优化至更低复杂度。

优化方案：二维差分矩阵法 #

该方法可将整体时间复杂度降至O(N²)，远低于原实现的O(N³)，核心思路是通过差分矩阵记录区域增量，最后用前缀和还原结果：

1. 初始化差分矩阵 #

创建一个(N+2)×(N+2)的差分矩阵diff（额外扩展两行两列是为了避免边界判断），所有元素初始化为0。

2. 处理每次子矩阵更新 #

对于每次输入的参数，仅需对差分矩阵执行4次O(1)的赋值操作：

diff[Row1][Col1] += Value
diff[Row1][Col2 + 1] -= Value
diff[Row2 + 1][Col1] -= Value
diff[Row2 + 1][Col2 + 1] += Value

N次更新的总时间复杂度为O(N)。

3. 计算前缀和还原最终矩阵 #

所有更新完成后，通过两次前缀和计算将差分矩阵转换为最终的增量矩阵，再与初始矩阵M累加得到结果：

1. 按行计算前缀和：

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

2. 按列计算前缀和：

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

3. 合并初始矩阵与增量矩阵：

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

这一步的时间复杂度为O(N²)。

原理说明 #

二维差分是前缀和的逆运算：通过在差分矩阵的四个顶点标记增量，后续的前缀和计算会自动将这些增量扩散到整个目标子矩阵区域，从而避免了逐个元素更新的冗余操作，将单批次区域更新的复杂度从O((Row2-Row1+1)*(Col2-Col1+1))降至O(1)。

内容的提问来源于stack exchange，提问作者C and Python lover