首页 > 试题广场 >

【模板】二维前缀和

[编程题]【模板】二维前缀和

热度指数：13315 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 给定一个由 $n$ 行 $m$ 列整数组成的矩阵 $\{a_{i,j}\}$ （下标均从 $1$ 开始）。
$\hspace{15pt}$ 现有 $q$ 次独立查询，第 $k$ 次查询给定四个整数 $x_1,y_1,x_2,y_2$ ，表示左上角坐标 $\left(x_1,y_1\right)$ 与右下角坐标 $\left(x_2,y_2\right)$ 满足 $1\leqq x_1\leqq x_2\leqq n$ 且 $1\leqq y_1\leqq y_2\leqq m$ 。
$\hspace{15pt}$ 请你计算该子矩阵中全部元素之和，记为

$\displaystyle S\bigl(x_1,y_1,x_2,y_2\bigr)=\sum_{i=x_1}^{x_2}\,\sum_{j=y_1}^{y_2} a_{i,j}$ 。

$\hspace{15pt}$ 你需要依次回答所有查询。

输入描述:

在一行上输入三个整数 ，依次表示矩阵的行数、列数与查询次数。
此后  行，每行输入  个整数 ，表示矩阵第  行的元素；共计  个整数。
此后  行，每行输入四个整数 ，所有变量均满足

。

输出描述:

对于每一次查询，在一行上输出一个整数，表示对应子矩阵元素之和。

示例1

输入

输出

8
25
32

说明

以第一组样例中的第二次查询  为例：
查询的子矩阵包含矩阵的左上  区域；
其内部所有元素之和为 ；
因此输出 。

备注:

读入数据可能很大，请注意读写时间。

算法知识视频讲解

Java

BraveCoder

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int q = in.nextInt();

        // 原始矩阵使用1-based索引
        long[][] matrix = new long[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                matrix[i][j] = in.nextLong();
            }
        }

        // 构建前缀和数组
        long[][] prefix = new long[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                prefix[i][j] = matrix[i][j] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];
            }
        }

        // 处理查询，直接打印每个结果
        while (q-- > 0) {
            int x1 = in.nextInt();
            int y1 = in.nextInt();
            int x2 = in.nextInt();
            int y2 = in.nextInt();

            long sum = prefix[x2][y2] - prefix[x1 - 1][y2] - prefix[x2][y1 - 1] + prefix[x1 - 1][y1 - 1];
            System.out.println(sum); 
        }
    }
}

发表于 2025-09-09 20:06:39 回复(0)

Java

有一套的芝士面向对象

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //1.读入数据
        int n = in.nextInt(), m = in.nextInt(), q = in.nextInt();
        int[][] arr = new int[n + 1][m + 1];
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                arr[i][j] = in.nextInt();
        //2.处理数据
        long dp[][] = new long[n + 1][m + 1];
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + arr[i][j];
        while(q > 0){
            int x1 = in.nextInt(),y1 = in.nextInt(),x2 = in.nextInt(),y2 = in.nextInt();
            long x = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];
            System.out.println(x);
            q--;
        }
    }
}

发表于 2023-07-14 15:06:29 回复(0)

Java

牛客208400313号

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        int q = in.nextInt();
        int[][] matrix = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                matrix[i][j] = in.nextInt();
            }
        }

        // 前缀和数组（分开写便于理解），int[]会溢出
        long[][] preSum = new long[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 注意与matrix数组的索引偏移
                preSum[i][j] = matrix[i - 1][j - 1] + preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1];
            }
        }

        // 计算区间和
        for (int i = 0; i < q; i++) {
            int row1 = in.nextInt(), col1 = in.nextInt();
            int row2 = in.nextInt(), col2 = in.nextInt();
            // 注意与输入数据的索引偏移
            System.out.println(preSum[row2][col2] - preSum[row1 - 1][col2] - preSum[row2][col1 - 1] + preSum[row1 - 1][col1 - 1]);
        }

    }
}

发表于 2022-10-05 09:29:57 回复(0)

Java

wanbf

import java.util.Scanner;

public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
long q=sc.nextLong();
long[][] arr = new long[n+1][m+1];
for(int i=1;i<n+1;i++){
for(int j=1;j<m+1;j++){
arr[i][j] = arr[i-1][j]+arr[i][j-1]+sc.nextLong()-arr[i-1][j-1];
}
}
for(int i=0;i<q;i++){
int x1=sc.nextInt();
int y1=sc.nextInt();
int x2=sc.nextInt();
int y2=sc.nextInt();
long res = arr[x2][y2]-arr[x2][y1-1]-arr[x1-1][y2]+arr[x1-1][y1-1];
System.out.println(res);
}
}
}

发表于 2022-01-04 20:17:31 回复(0)