题目描述

二维前缀和

样例

import java.io.IOException;
import java.util.Scanner;

public class Main {
    private static final int N = 1010;
    private static final int[][] a = new int[N + 5][N + 5];
    private static final int[][] s = new int[N + 5][N + 5];

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int q = in.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                a[i][j] = in.nextInt();
            }
        }
        init(n, m);
        while (q-- > 0) {
            int x1 = in.nextInt();
            int y1 = in.nextInt();
            int x2 = in.nextInt();
            int y2 = in.nextInt();
            int res = sumPrefix(x1, y1, x2, y2);
            System.out.println(res);
        }
    }

    private static void init(int n, int m) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];//算[0,0]到[X1,Y1]
            }
        }
    }

    private static int sumPrefix(int x1, int y1, int x2, int y2) {
        return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];//算[X1,Y1]到[X2,Y2]
    }
}