题意整理。

  • 给定一个n行m列的矩阵。
  • 有q次查询，每次查询给定子矩阵的左上角坐标和右下角坐标，输出子矩阵中所有元素的累加和。

方法一（二维前缀和）

1.解题思路

  • 首先对矩阵进行预处理，得到对应的前缀和矩阵。
  • 利用前缀和矩阵相应区域的加减运算，即可得到对应子矩阵中所有元素的累加和。

图解展示（图中presum[3][4]除了包括绿色部分，还包括其它重叠的部分，其它几项也一样，另外presum[1][1]被多减了一次，所以最后要加一次）： alt

2.代码实现

import java.util.*;

public class Main {
    public static void main(String[] args){
        //标准输入
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();
        
        //定义并初始化矩阵
        int[][] arr=new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                arr[i][j]=sc.nextInt();
            }
        }
        
        //定义并初始化二维前缀和
        long[][] presum=new long[n+1][m+1];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                presum[i+1][j+1]=presum[i+1][j]+presum[i][j+1]-presum[i][j]+arr[i][j];
            }
        }
        
        //q次查询
        while(q-->0){
            //查询子矩阵的左上角和右下角坐标
            int x1=sc.nextInt();
            int y1=sc.nextInt();
            int x2=sc.nextInt();
            int y2=sc.nextInt();
            System.out.println(presum[x2][y2]-presum[x2][y1-1]-presum[x1-1][y2]+presum[x1-1][y1-1]);
        }
        
       
    }
}

3.复杂度分析

  • 时间复杂度：需要遍历数组中所有元素构建前缀和数组，预处理的时间复杂度为O(n∗m)O(n*m)，每次查询只需进行一次运算，所以查询的时间复杂度为O(1)O(1)。
  • 空间复杂度：需要额外长度为(n+1)∗(m+1)(n+1)*(m+1)的前缀和矩阵，所以空间复杂度为O(n∗m)O(n*m)。