二维前缀和

二维前缀和（2D Prefix Sum）是对一个二维矩阵进行预处理，以便可以快速地回答某个子矩阵的和。该预处理过程可以在 $O(n^2)$ 的时间复杂度内完成，每次查询子矩阵的和只需要 $O(1)$ 的时间。

具体实现方法如下：

1. 对于原始的二维矩阵 $matrix$，先计算出一个新的二维矩阵 $prefix$，其中 $prefix[i][j]$ 表示从矩阵左上角到 $(i,j)$ 这个位置所组成的子矩阵的所有元素之和。

2. 对于任意一个子矩阵 $[x_1,x_2][y_1,y_2]$，其元素之和可以通过下面的公式计算得出：

   sum = prefix[x2][y2] - prefix[x2][y1-1] - prefix[x1-1][y2] + prefix[x1-1][y1-1]

其中，$prefix[x2][y2]$ 表示整个矩阵的元素之和，$prefix[x2][y1-1]$ 和 $prefix[x1-1][y2]$ 分别表示左侧和上侧的元素之和，而 $prefix[x1-1][y1-1]$ 则被减去了两次，因此需要加回来。

下面是一个简单的 Python 代码实现，其中假设原始矩阵的大小为 $n \times m$：

def prefix_sum(matrix):
    n, m = len(matrix), len(matrix[0])
    prefix = [[0] * (m+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, m+1):
            prefix[i][j] = matrix[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]
    return prefix

def query_sum(prefix, x1, y1, x2, y2):
    return prefix[x2][y2] - prefix[x2][y1-1] - prefix[x1-1][y2] + prefix[x1-1][y1-1]

可以看到，二维前缀和的实现非常简单，但却非常实用，可以在很多需要计算子矩阵和的场合发挥作用，比如图像处理、矩阵计算等等。