零基础学算法100天第5天——二维前缀和（基础算法）

⭐️引言⭐️

大家好啊，我是执梗。上一篇文章详细的介绍了一维前缀和的预处理和使用。今天我们讲解的是二维前缀和。这个考点在今年十三届蓝桥杯C++B组省赛是出现过该考点的（末尾习题会讲解），所以还是非常重要的一个知识点。但其实掌握好了一维，拓展到二维也还是不难的。

一维前缀和：零基础学算法100天第4天——前缀和（基础算法）

⭐️目录⭐️

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

其中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];
            }
        }

🎃 4.前缀和数组的使用

知道预处理的原理，那么使用起来就非常简单啦。还是根据图解帮助大家快速理解。

我们从这几个图来分析，蓝色矩阵是我们的目标求和矩阵，我们并无法直接通过二维数组求出来，我们设蓝色矩阵左上角的坐标为x1，y1以及右下角坐标为x2，y2。 我们可以先通过红色矩阵然后减去两个绿色的矩阵，其中黄色矩阵被减去了两次，所以我们还需要再加回来一次。

所以已知两点坐标求该矩阵和的公式为：

$s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]$

这个公式再次体现了为什么下标都要从1开始的好处，防止越界问题。

🍋5.二维前缀和模板题练习

1）、二维区域和检索

题目链接：二维区域和检索 – 矩阵不可变

和一维前缀和那题是一模一样的，只不过变成了二维状态，直接预处理出二维前缀和数组，再利用公式即可，要注意我们接收的数组下标是从0开始的。

代码转换：

class NumMatrix {
    int[][] arr;
    public NumMatrix(int[][] matrix) {
        int n=matrix.length;
        if(n>0){
        int m=matrix[0].length;     
        arr=new int[n+1][m+1];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                arr[i+1][j+1]=arr[i][j+1]+arr[i+1][j]-arr[i][j]+matrix[i][j];
            }
        }
    }
}
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return  arr[row2+1][col2+1]-arr[row1][col2+1]-arr[row2+1][col1]+arr[row1][col1];
    }
}

2）、统计子矩阵

给定一个 N × M 的矩阵 A，请你统计有多少个子矩阵 (最小 1 × 1，最大 N × M) 满足子矩阵中所有数的和不超过给定的整数 K?

题目链接：蓝桥杯2022年第十三届省赛真题-统计子矩阵 – C语言网

这道题是今年B++组中间的一道题目，几乎就是纯裸的二维前缀和题目，只不过如果不能拿满分，但还是能拿大部分的分，而且直接套模板就行，根本不需要怎么变形，这种分数的性价比更高。

直接对原数组进行前缀和数组预处理，然后枚举左上角的坐标和右下角的坐标计算即可。