求二维数组的前缀和？

和是一种重要的预处理，能大大降低查询的时间复杂度。我们可以简单理解为“数列的前 n 项的和”。这个概念其实很容易理解，即一个数组中，第 n 位存储的是数组前 n 个数字的和。

通过一个例子来进行说明会更清晰。题目描述：有一个长度为 N 的整数数组 A，要求返回一个新的数组 B，其中 B 的第 i 个数 B[i]是「原数组 A 前 i 项和」。

这道题实际就是让你求数组 A 的前缀和。对 [1,2,3,4,5,6] 来说，其前缀和可以是 pre=[1,3,6,10,15,21]。我们可以使用公式 pre[??]=pre[???1]+nums[??]得到每一位前缀和的值，从而通过前缀和进行相应的计算和解题。其实前缀和的概念很简单，但困难的是如何在题目中使用前缀和以及如何使用前缀和的关系来进行解题。实际的题目更多不是直接让你求前缀和，而是你需要自己「使用前缀和来优化算法的某一个性能瓶颈」。

而如果数组是正数的话，前缀和数组会是一个单调不递减序列，因此前缀和 + 二分也会是一个考点，不过这种题目难度一般是力扣的困难难度。关于这个知识点，我会在之后的「二分专题」方做更多介绍。

简单的二维前缀和

上面提到的例子是一维数组的前缀和，简称一维前缀和。那么二维前缀和实际上就是二维数组上的前缀和了。一维数组的前缀和也是一个一维数组，同样地，二维数组的前缀和也是一个二维的数组。

比如对于如下的一个二维矩阵：

 

如我们想要求 ，则可以通过 的方式来实现。这样我就可以通过 的预处理计算二维前缀和矩阵(m 和 n 分别为矩阵的长和宽)，再通过 的时间计算出「任意小矩阵的和」。其底层原理就是上面提到的容斥原理，大家可以通过画图的方式来感受一下。

如何将二维前缀和转化为一维前缀和

然而实际上，我们也可不构建一个前缀和数组，而是直接原地修改。

一维前缀和同样可以采用这一技巧。

比如我们可以先不考虑行之间的关联，而是预先计算出每一行的前缀和。对于计算每一行的前缀和就是「一维前缀和」啦。接下来通过「固定两个列的端点」的方式计算每一行的区域和。代码上，我们可以通过三层循环来实现， 其中两层循环用来固定列端点，另一层用于枚举所有行。

其实也可以反过来。即固定行的左右端点并枚举列，下面的题目会提到这一点。

（编辑：东莞站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!