题目描述
Java-快读快写
样例
import java.io.*;
import java.util.*;
public class Main {
static int N = 1010;
static int arr[][] = new int[N][N];
static int sum[][] = new int[N][N];
static int n;
static int m;
static int q;
static int x1,y1,x2,y2;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
q = Integer.parseInt(st.nextToken());
for(int i = 1; i <= n; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 1; j <= m; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
/*
* sum[i][j]的值是:1到i行 1到j列 所有值的和
* 1. 先加上当前值
* 2. 加上上一行,即上一个格子的sum值(就是 1到i-1行 1到j列 所有值的和
* 3. 加上左一列,即左一个格式的sun值(就是 1到i行 1到j-1列 所有值的和
* 4. 因为步骤2.3.叠加后,会有重复的值是sum中曾经加过的,所以需要去掉这一部分重复值
* 这部分重复值就是:i-1行 j-1列所有格子的值,所以减去 sum[i-1][j-1]
* */
sum[i][j] = arr[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}
}
for(int i = 0; i < q; i++) {
st = new StringTokenizer(br.readLine());
x1 = Integer.parseInt(st.nextToken());
y1 = Integer.parseInt(st.nextToken());
x2 = Integer.parseInt(st.nextToken());
y2 = Integer.parseInt(st.nextToken());
/*
* 通过前面对sum的计算可得知,某个格子的sum就是该格子 前i行j列所有值的和
* 计算子矩阵和 原理:
* 1. 通过子矩阵的右下标 x2 y2 得到 该位置前x2行y2列所有值的和
* 2. 减去子矩阵右上角格子的上面一个格子,就能把子矩阵上面的所有值减去
* 3. 减去子矩阵左下角格子的左边一个格子,就能把子矩阵左边的所有值减去
* 4. 通过2.3减去了上面和左边的所有值,但是会发现上面和左边有一部分格子是重复的,相当于我们减了两次
* 5. 所以需要加上这部分重复的值,即:加上子矩阵左上角左上一个格子的值,该位置就是sum[x1-1][y1-1]
* */
int result = sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
bw.write(result + "\n");
}
bw.flush();
br.close();
bw.close();
}
}