⭐️引言⭐️

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

              一维前缀和:零基础学算法100天第4天——前缀和(基础算法)

⭐️目录⭐️

🔥1.背景小故事

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

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

🎃 4.前缀和数组的使用

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

        1)、二维区域和检索

        2)、统计子矩阵


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

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

        代码转换:

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;
    }
}

如果文章对你有所帮助,还望能给点三连支持一下,非常感谢!!!

Logo

旨在为数千万中国开发者提供一个无缝且高效的云端环境,以支持学习、使用和贡献开源项目。

更多推荐