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;}}