二维前缀和，建立在一维前缀和之上，我们要求一个矩阵内一个任意的子矩阵的数的和，我们就可以用二维前缀和。

我们可以感性的将其理解为建立在二维平面上的前缀和，如下图：

红色区域所有数的和即为二维前缀和中点（i,j) 的值。

一、如何预处理

类比一维前缀和，我们可以在O(n)的时间复杂度下预处理，如下代码：

    s[i] = s[i-1] + a[i];

那么对于二维前缀和，我们怎么预处理呢？

先给出算式：

    Map[i][j] + Map[i-1][j] + Map[i][j-1] - Map[i-1][j-1] + a[i][j];

（a 数组是原数据数组，Map数组用于存放前缀和）

类比一维前缀和，因为我们从左到右在计算 a[i] 的时候已经知道了a[i-1] 的值，所以同理，我们从左上向右下在计算 Map[i][j] 的时候已经知道了它右上所有点的前缀和，也就是知道 Map[i-1][j]、Map[i][j-1] 和 Map[i-1][j-1] 的值，那么现在考虑为什么要做如上的运算。

其中，Map[i][j] 的初始值即为点 (i,j) 的权值，如图：

那么现在，我们要求前缀和，也就是要加上下图中橙色区域：

而我们加上的 Map[i-1][j] 即为下图蓝色区域：

加上的 Map[i][j-1] 即为下图绿色区域：

然后我们会发现，有一部分重叠了，如下图紫色区域：

而这部分就是我们要减去的 Map[i-1][j-1] 。

那么我们的预处理就完成了。

时间复杂度：O(n×m)，与一维中的O(n)预处理同理。

二、如何查询

依然是类比一维前缀和，对于查询区间 (l,r) 的值，我们可以用如下代码进行 O(1) 的查询：

    sum=a[r]-a[l-1];

也就是说，用右端点的前缀和值减去左端点 -1 的前缀和值即得到了区间 (l,r) 的和，如下图：

那么对于二维前缀和，我们有应该怎么办呢？

对于计算矩形(x1,y1)∼(x2,y2)的和，先给出如下算式：

    sum = Map[x2][y2] - Map[x1-1][y2] - Map[x2][y1-1] + Map[x1-1][y1-1];

下面来理解算式：

现在我们要求下图中红色区域的权值和：

而我们已经预处理好了前缀和，但是我们还不直接知道矩形(x1,y1)∼(x2,y2)的权值和，那么我们考虑怎么减去那部分。

我们已经知道了 Map[x2][y2] ，而我们需要减去下图中橙色区域：

那么我们先减去 Map[x1−1][x2] ，也就是下图中蓝色区域：

然后再减去 Map[x2][y1−1] ，也就是下图中绿色区域：

然后，我们发现我们多减去了一部分，要把它加回来，而这部分就是 Map[x1−1][y1−1] ，如下图紫色部分：

这样，我们就成功的得到了需要求和的部分的值。

时间复杂度：O(1)，与一维前缀和的 O(1) 同理。