题解 | 【模板】二维前缀和

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());

        long[][] matrix = new long[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= m; j++) {
                matrix[i][j] = Long.parseLong(st.nextToken());
            }
        }

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

        for (int k = 0; k < q; k++) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

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

        out.flush();
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. 输入处理：使用 BufferedReader 和 StringTokenizer 高效读取输入数据。
2. 矩阵初始化：将输入的矩阵存储在 matrix 数组中，下标从 1 开始。
3. 构建前缀和数组：通过递推公式计算每个位置的前缀和，确保每个位置的值正确表示从 (1,1) 到该位置的子矩阵和。
4. 处理查询：对于每个查询，使用前缀和数组快速计算子矩阵的和，并利用 PrintWriter 高效输出结果。