零基础学算法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为前缀和数组，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。 我们可以先通过红色矩阵然后减去两个绿色的矩阵，其中黄色矩阵被减去了两次，所以我们还需要再加回来一次。
所以已知两点坐标求该矩阵和的公式为：
这个公式再次体现了为什么下标都要从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?
这道题是今年B++组中间的一道题目，几乎就是纯裸的二维前缀和题目，只不过如果不能拿满分，但还是能拿大部分的分，而且直接套模板就行，根本不需要怎么变形，这种分数的性价比更高。
直接对原数组进行前缀和数组预处理，然后枚举左上角的坐标和右下角的坐标计算即可。
代码转换：
import java.util.Scanner;
public class Main {
static int N=510;
static int[][] a=new int[N][N];
static int[][] s=new int[N][N];
static int res=0;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
int k=sc.nextInt();
for (int i = 1; i <=n; i++) {
for (int j = 1; j <=m; j++) {
a[i][j]=sc.nextInt();
}
}
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];
}
}
//枚举左上角坐标
for (int i = 1; i <=n; i++) {
for (int j = 1; j <=m; j++) {
//枚举右下标
for (int l = i; l <=n; l++) {
for (int o = j; o <=m; o++) {
if (check(i,j,l,o,k)) res++;
else break;
}
}
}
}
System.out.println(res);
}
//判断该矩阵和是否小于k
static boolean check(int x1,int y1,int x2,int y2,int k){
int h=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
return h<=k;
}
}如果文章对你有所帮助，还望能给点三连支持一下，非常感谢！！！
旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。
更多推荐
101
0- 0
已为社区贡献5条内容
所有评论(0)