题解 | 【模板】二维前缀和

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n=scan.nextInt();//矩阵行数
        int m=scan.nextInt();//矩阵列数
        int q=scan.nextInt();//查询次数
	  //1.初始化矩阵  下标从1开始,防止越界访问
        int[][] arr=new int[n+1][m+1];
        for(int i=0;i<n+1;i++){
            for(int j=0;j<m+1;j++){
                if(i==0||j==0){
                    arr[i][j]=0;   //这里其实不必要对0再赋值,默认就是0,可以直接从下标为1开始赋值
                }else arr[i][j]=scan.nextInt();
            }
        }
	  // 构造 前缀和 数组矩阵,
        long[][] dp=new long[n+1][m+1];//定义为long,防溢出
        for(int i=0;i<n+1;i++){
            for(int j=0;j<m+1;j++){
                if(i==0||j==0){
                    dp[i][j]=0;
                }else{
                    dp[i][j]=dp[i][j-1]+dp[i-1][j]+arr[i][j]-dp[i-1][j-1];
                }
            }
        }
        while(q>0){
            int x1=scan.nextInt();
            int y1=scan.nextInt();
            int x2=scan.nextInt();
            int y2=scan.nextInt();
            long ret=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1];
            System.out.println(ret);
            q--;
        }

    }
}

时间复杂度:O(m*n)+O(q)

构造前缀和矩阵: O(m*n),遍历一遍数组

对q次求和:O(q)