算法之二维前缀和

package com.zhang.reflection.面试.算法模版.前缀和;
import java.util.Scanner;
/**
 * 给你一个 n 行 m 列的矩阵 A ，下标从1开始。
 *
 * 接下来有 q 次查询，每次查询输入 4 个参数 x1 , y1 , x2 , y2
 *
 * 请输出以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和，
 *
 * 输入：
 * 3 4 3（n,m,q）
 * 1 2 3 4
 * 3 2 1 0
 * 1 5 7 8
 * 1 1 2 2
 * 1 1 3 3
 * 1 2 3 4
 * 输出：
 * 8
 * 25
 * 32
 */

public class 二维前缀和 {
    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+1][m+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                arr[i][j]=sc.nextInt();
            }
        }
        //定义并初始化二维前缀和,每个二维前缀和记录的是自己+自己左边+自己右边的和
        long[][] presum=new long[n+1][m+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                presum[i][j]=presum[i-1][j]+presum[i][j-1]-presum[i-1][j-1]+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]);
        }
    }
}