二维前缀和

二维前缀和（2D Prefix Sum）是指对于一个二维数组，通过预处理得到一个新的数组，该数组中每个元素的值为原数组中以该元素为右下角的子矩阵的所有元素之和。其可以用于快速计算出二维矩阵区域和。

具体实现方法为，先预处理出一个二维前缀和数组，然后通过该数组计算出任意两个坐标所确定的矩形区域的和。

下面给出 C++ 实现代码供参考：

const int MAXN = 1005;
int a[MAXN][MAXN], s[MAXN][MAXN];

// 计算二维前缀和
void prefix_sum(int n, int m) {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }
}

// 计算以 (x1, y1) 为左上角，以 (x2, y2) 为右下角的矩形区域的和
int query(int x1, int y1, int x2, int y2) {
    return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
}

其中，`a` 数组是原始的二维数组，`s` 数组是计算得到的二维前缀和数组。`prefix_sum` 函数用于计算二维前缀和，`query` 函数用于查询任意矩形区域的和。