题目描述
输入一个 n 行 m 列的整数矩阵,再输入 q 个询问,每个询问包含四个整数 x1,y1,x2,y2,表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数 n,m,q。
接下来 n 行,每行包含 m 个整数,表示整数矩阵。
接下来 q 行,每行包含四个整数 x1,y1,x2,y2,表示一组询问。
输出格式
共 q 行,每行输出一个询问的结果。
数据范围
1≤n,m≤1000,
1≤q≤200000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤矩阵内元素的值≤1000
样例
输入样例:
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
输出样例:
17
27
21
前缀和
一维数组
一维数组前缀和:
S[i] = a[1] + a[2] + … a[i]
某段区间长度的和:
a[l] + … + a[r] = S[r] - S[l - 1]
二维数组
二维数组前缀和(S[i, j] = 第i行j列格子左上部分所有元素的和):
s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + arr[i][j]
二维数组子矩阵和(以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和):
res = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/*
子矩阵的和
*/
public class Main {
public static void main(String[] args) throws IOException {
//输入矩阵行 n 列 m,查询次数 q
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
int n = Integer.parseInt(s1[0]);
int m = Integer.parseInt(s1[1]);
int q = Integer.parseInt(s1[2]);
//输入二维数组元素
int arr[][] = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
String[] s2 = br.readLine().split(" ");
for (int j = 1, t = 0; j <= m && t < m; j++, t++) {
arr[i][j] = Integer.parseInt(s2[t]);
}
}
//定义二维前缀和
int s[][] = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + arr[i][j];
}
}
//输入询问区间范围并输出结果
while (q-- > 0) {
String[] s2 = br.readLine().split(" ");
int x1 = Integer.parseInt(s2[0]);
int y1 = Integer.parseInt(s2[1]);
int x2 = Integer.parseInt(s2[2]);
int y2 = Integer.parseInt(s2[3]);
//子矩阵和
int res = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
System.out.println(res);
}
}
}