求生成二维前缀和矩阵的算法：从矩阵m得到矩阵r

问题定义 #

给定一个二维矩阵m，生成对应的矩阵r，其中r[i][j]的值等于m中从左上角(0,0)到(i,j)的矩形区域内所有元素的总和。

示例说明 #

输入矩阵m： #

1 2 3
4 5 6
7 8 9

生成的前缀和矩阵r： #

1  3  6
5  12 21
12 27 45

计算示例： #

• r[1][1] = m[0][0] + m[0][1] + m[1][0] + m[1][1] = 1+2+4+5=12
• r[2][1] = m[0][0] + m[0][1] + m[1][0] + m[1][1] + m[2][0] + m[2][1] = 1+2+4+5+7+8=27

算法思路 #

直接暴力计算每个点的矩形和会重复累加大量元素，时间复杂度为O(nm(i+1)(j+1))，效率极低。我们可以用动态规划优化，将时间复杂度降到O(nm)，核心思路是利用已计算的前缀和推导当前值：

1. 边界处理：
   • 左上角元素：r[0][0] = m[0][0]
   • 第一行：r[0][j] = r[0][j-1] + m[0][j]（累加左侧所有元素）
   • 第一列：r[i][0] = r[i-1][0] + m[i][0]（累加上方所有元素）
2. 内部元素计算：
   对于任意i>0且j>0的位置，利用以下公式：

   r[i][j] = m[i][j] + r[i-1][j] + r[i][j-1] - r[i-1][j-1]
   

   解释：r[i-1][j]是上方矩形的和，r[i][j-1]是左侧矩形的和，两者相加会重复计算左上角r[i-1][j-1]的区域，所以需要减去一次，再加上当前元素m[i][j]，就得到了从(0,0)到(i,j)的矩形总和。

代码实现（Python） #

def generate_prefix_matrix(m):
    if not m or not m[0]:
        return []
    rows = len(m)
    cols = len(m[0])
    # 初始化前缀和矩阵
    r = [[0]*cols for _ in range(rows)]
    
    # 左上角元素
    r[0][0] = m[0][0]
    
    # 填充第一行
    for j in range(1, cols):
        r[0][j] = r[0][j-1] + m[0][j]
    
    # 填充第一列
    for i in range(1, rows):
        r[i][0] = r[i-1][0] + m[i][0]
    
    # 填充内部元素
    for i in range(1, rows):
        for j in range(1, cols):
            r[i][j] = m[i][j] + r[i-1][j] + r[i][j-1] - r[i-1][j-1]
    
    return r

# 测试示例
m = [
    [1,2,3],
    [4,5,6],
    [7,8,9]
]
r = generate_prefix_matrix(m)
# 打印结果
for row in r:
    print(' '.join(map(str, row)))

运行结果 #

执行上述代码后，输出与示例中的r矩阵一致：

1 3 6
5 12 21
12 27 45

内容的提问来源于stack exchange，提问作者Ξ R Λ Z Ξ R