题目描述

子矩阵的和

模板：

初始化 前缀和 数组

s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];

计算二维前缀和

//[x2,y2] 为整个前缀和总和, 减去左半边和右半边后,
//[x1,y1]区间被减了两次所以再加上[x1,y1]
s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]

JAVA 代码

import java.util.*;
import java.io.*;

class Main{

    public static void main(String args[]) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));


        String[] s1 = in.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int m = Integer.parseInt(s1[1]);
        int q = Integer.parseInt(s1[2]);
        int[][] a = new int[n+1][m+1];
        int[][] s = new int[n+1][m+1];


        for(int i = 1; i<=n;i++){
            String[] s2 = in.readLine().split(" ");
            for(int j = 1; j<=m; j++){
                //初始化 a 数组
                a[i][j] = Integer.parseInt(s2[j-1]);
                //初始化 前缀和 数组
                s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
            }
        }


        while(q-->0){
            String[] s3 = in.readLine().split(" ");
            int x1 = Integer.parseInt(s3[0]);
            int y1 = Integer.parseInt(s3[1]);
            int x2 = Integer.parseInt(s3[2]);
            int y2 = Integer.parseInt(s3[3]);

            //计算二维前缀和
            //[x2,y2] 为整个前缀和总和, 减去左半边和右半边后, 
            //[x1,y1]区间被减了两次所以再加上[x1,y1]
            System.out.println(s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);
        }



    }

}