前缀和例题:子矩阵的和AcWing796-Java版

//前缀和模板提,在读入数据的时候就可以先算好前缀和的大小
//计算前缀的时候用:g[i][j] = g[i][j-1] + g[i-1][j] - g[i-1][j-1] + Integer.parseInt(init[j-1]);
//计算结果的时候用:g[x2][y2] - g[x1 - 1][y2]- g[x2][y1-1] + g[x1 -1][y1 - 1] + "\n"
//一些重复加的地方都需要减掉,如计算前缀和的时候g[i-1][j-1]包括在了前面的g[i][j-1] + g[i-1][j],多减去一次
//g[x1 - 1][y1 - 1]也被包括在前面两项表达式,只需减去一次

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;public class Main{static int n,m,q;static int N = 1010;static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));static int[][] g = new int[N][N];public static void main(String[] args) throws IOException{String[] init = in.readLine().split(" ");n = Integer.parseInt(init[0]);m = Integer.parseInt(init[1]);q = Integer.parseInt(init[2]);for(int i = 1;i <= n;i ++) {init = in.readLine().split(" ");for(int j = 1;j <= m;j ++) {g[i][j] = g[i][j-1] + g[i-1][j] - g[i-1][j-1] + Integer.parseInt(init[j-1]);}}while(q-- > 0) {init = in.readLine().split(" ");int x1 = Integer.parseInt(init[0]);int y1 = Integer.parseInt(init[1]);int x2 = Integer.parseInt(init[2]);int y2 = Integer.parseInt(init[3]);out.write(g[x2][y2] - g[x1 - 1][y2]- g[x2][y1 - 1] + g[x1 -1][y1 - 1] + "\n");}in.close();out.flush();}}

前缀和例题:一维版前缀和

进阶版:二维前缀和-2