西安网站改版的公司,软件外包是什么意思,接网站开发私活如何签合同,响应式网站怎样做Problem: 796. 子矩阵的和 文章目录 思路解题方法复杂度Code 思路 这是一个二维前缀和的问题。二维前缀和的主要思想是预处理出一个二维数组#xff0c;使得每个位置(i, j)上的值表示原数组中从(0, 0)到(i, j)形成的子矩阵中所有元素的和。这样#xff0c;对于任意的子矩阵(x… Problem: 796. 子矩阵的和 文章目录 思路解题方法复杂度Code 思路 这是一个二维前缀和的问题。二维前缀和的主要思想是预处理出一个二维数组使得每个位置(i, j)上的值表示原数组中从(0, 0)到(i, j)形成的子矩阵中所有元素的和。这样对于任意的子矩阵(x1, y1)到(x2, y2)我们可以通过四个前缀和的值快速计算出其和。 解题方法 1.首先我们需要读入矩阵的大小和矩阵的元素值。 2.然后我们计算二维前缀和。对于每个位置(i, j)其前缀和的值等于其上方元素的前缀和加上其左方元素的前缀和再减去其左上方元素的前缀和最后加上其自身的值。 3.最后对于每个查询我们可以通过四个前缀和的值快速计算出子矩阵的和。 复杂度
时间复杂度: 预处理的时间复杂度为 O ( n ∗ m ) O(n*m) O(n∗m)其中 n n n和 m m m分别为矩阵的行数和列数。 每次查询的时间复杂度为 O ( 1 ) O(1) O(1)。 空间复杂度: 我们需要额外的 O ( n ∗ m ) O(n*m) O(n∗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;}}
