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

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