796. 子矩阵的和

Problem: 796. 子矩阵的和

思路

这是一个二维前缀和的问题。二维前缀和的主要思想是预处理出一个二维数组，使得每个位置(i, j)上的值表示原数组中从(0, 0)到(i, j)形成的子矩阵中所有元素的和。这样，对于任意的子矩阵(x1, y1)到(x2, y2)，我们可以通过四个前缀和的值快速计算出其和。

解题方法

1.首先，我们需要读入矩阵的大小和矩阵的元素值。
2.然后，我们计算二维前缀和。对于每个位置(i, j)，其前缀和的值等于其上方元素的前缀和加上其左方元素的前缀和，再减去其左上方元素的前缀和，最后加上其自身的值。
3.最后，对于每个查询，我们可以通过四个前缀和的值快速计算出子矩阵的和。

复杂度

时间复杂度:

预处理的时间复杂度为$O(n\ast m)$，其中$n$和$m$分别为矩阵的行数和列数。
每次查询的时间复杂度为$O(1)$。

空间复杂度:

我们需要额外的$O(n\ast m)$的空间来存储前缀和。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
	static StreamTokenizer sr = new StreamTokenizer(in);
	static int n, m, q;
	static int MAXN = 1001;
	static int MAXM = 1001;
	static int[][] arr = new int[MAXN][MAXM];

	public static void main(String[] args) throws IOException {
		n = nextInt();
		m = nextInt();
		q = nextInt();
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				arr[i][j] = nextInt();
			}
		}
		for (int i = 1; i <= n; i++) {
			arr[i][0] += arr[i - 1][0];
		}
		for (int j = 1; j <= m; j++) {
			arr[0][j] += arr[0][j - 1];
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				arr[i][j] += arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1];
			}
		}
		while (q-- > 0) {
			int x1 = nextInt();
			int y1 = nextInt();
			int x2 = nextInt();
			int y2 = nextInt();
			out.println(arr[x2][y2] - arr[x2][y1 - 1] - arr[x1 - 1][y2] + arr[x1 - 1][y1 - 1]);

		}
		out.flush();

	}

	static int nextInt() throws IOException {
		sr.nextToken();
		return (int) sr.nval;
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54