#yyds干货盘点# 动态规划专题：二维前缀和

1.简述：

给你一个 n 行 m 列的矩阵 A ，下标从1开始。接下来有 q 次查询，每次查询输入 4 个参数 x1 , y1 , x2 , y2请输出以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和，

第一行包含三个整数n,m,q.接下来n行，每行m个整数，代表矩阵的元素接下来q行，每行4个整数x1, y1, x2, y2，分别代表这次查询的参数

输出q行，每行表示查询结果。

输入：

3 4 3
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

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