🎃 4.前缀和数组的使用
知道预处理的原理，那么使用起来就非常简单啦。还是根据图解帮助大家快速理解。
我们从这几个图来分析，蓝色矩阵是我们的目标求和矩阵，我们并无法直接通过二维数组求出来，我们设蓝色矩阵左上角的坐标为x1，y1以及右下角坐标为x2，y2。 我们可以先通过红色矩阵然后减去两个绿色的矩阵，其中黄色矩阵被减去了两次，所以我们还需要再加回来一次。
所以已知两点坐标求该矩阵和的公式为：
这个公式再次体现了为什么下标都要从1开始的好处，防止越界问题。
🍋5.二维前缀和模板题练习
1）、二维区域和检索
题目链接：二维区域和检索 - 矩阵不可变https://leetcode.cn/problems/range-sum-query-2d-immutable/
和一维前缀和那题是一模一样的，只不过变成了二维状态，直接预处理出二维前缀和数组，再利用公式即可，要注意我们接收的数组下标是从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语言网https://www.dotcpp.com/oj/problem2659.html
这道题是今年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; } }
