🔥1.背景小故事

           话说到上回的小兔子兔八哥借助小黑兔教学的一维前缀和，很很轻松的完成了妈妈给个任务，每次能在O（1）的时间复杂度内就得到一段区间的和。但是很快兔妈妈就有了新招，它将原来只有一行的萝卜坑变成了一个NxM的一个矩阵。每次兔妈妈会给定两个坐标x1、y1和x2、y2，要求兔八哥能快速地计算出以x1、y1为左上角，x2、y2为右下角组坐标的矩阵中有多少胡萝卜？

          兔八哥心想——这还不简单？

          由于总共有N行萝卜坑，兔八哥对每一行的萝卜坑都进行前缀和处理，相当于获得了N个一维前缀和数组。对于兔妈妈给定的子矩阵，如果该子矩阵有n行，我们只需要做n次一维前缀和运算，算出每行有多少个萝卜，然后加起来即可。由于有n行，每一行计算的时间复杂度是O(1)，所以复杂度为O（n）。兔八哥心想我真是太聪明了！如果对这个矩阵一个个萝卜坑数下去，那么复杂度就是O(nm)，这实在是太恐怖了！（n是行数，m是列数）。

         但是兔八哥很快就发现了问题！

         如果自己对行做前缀和处理，当列数很大的情况，O(n)的时间复杂度仍然无法接受，反过来处理列也是同理，每次还没算出来兔妈妈就已经等不及睡着了。

         有没有办法能像一维前缀和一样在O(1)时间复杂度内得到结果？

         兔八哥想起了自己的好兄弟——小黑兔！小黑兔很快发来回信——当然可以！二维前缀和就可以你的烦恼！！

🔆2.什么是二维前缀和？

       二维是从一维进行拓展，我们先从一维开始讲起。

        可以看出一维的前缀和数组，s[i]代表的是一段一维区间的长度，比如s[3]是原数组a中前3个元素之和，那么s[i]代表的是前i个元素之和。此时我们将其拓展为二维——那么二维前缀和数组s[i][j]代表的是什么呢？        

         S[i][j]代表的是以左上坐标为[1,1]右下角坐标为[i][j]的子矩阵之和。          

         当我们有如下一个二维数组a[][]：

1.假设我们已经有了该数组的前缀和数组，那么s[3][3]代表的是那个子矩阵的和呢？

根据前面的定义，应该是如下红色部分的矩阵之和，以坐标1,1为左上角，3,3为右下角的矩阵。

2.为什么横纵坐标要从1开始？

           这个原因和一维是同理的，就是防止出现边界问题，我们的前缀和数组一定要空出来，如果是ACM模式下，那我们原数组存放数据时最好就将其从下标为1开始存放。当时力扣刷题时传入的数组默认是从0开始的，此时我们预处理的时候需要稍微注意一下，后续讲解我将默认原数组下标为1讲解。    

😾3.如何预处理得到二维前缀和数组

         二维前缀和的预处理也非常简单，大家通过一个图的讲解就可以清楚了。

         我们就以前面的图为例，假设我们想得到s[3][3]的值，也就是红色矩阵的和。我们考虑它是由哪些已知总和的矩阵拼接起来的。

       从上面的板块来看，我们想得到红色的板块，可以发现它是由两块绿色的板块相加再加上单独蓝色的一块，但发现由于绿色板块存在重复的部分（黄色板块），所以我们需要减去一个黄色板块。由此可以得知前缀和的预处理公式为：

       其中s为前缀和数组，a为原数组。、

有的人肯定有疑问——你算s[i][j]的时候，怎么知道s[i-1][j]、s[i][j-1]、s[i-1][j-1]的值呢？

       这不用担心，我们在初始化前缀和数组的时候，是从上到下，从左到右来计算的，当你计算到s[i][j]时，它前面的状态都是已经被计算过的，可以直接使用。由此我们前缀和数组的初始化可以写成如下代码：

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]+a[i][j]-s[i-1][j-1];
            }
        }