leetcode/src/RangeSumQuery2D.java at master · LeBW/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 304. Range Sum Query 2D - Immutable
 * 二维数组，二位前缀和
 * @author LBW
 */
public class RangeSumQuery2D {
    private int m;
    private int n;
    private int[][] sum;

    public RangeSumQuery2D(int[][] matrix) {
        this.m = matrix.length;
        if (m == 0)
            return;
        this.n = matrix[0].length;
        this.sum = new int[m][n];
        int cur = 0;
        for (int i = 0; i < m; i++) {
            cur += matrix[i][0];
            sum[i][0] = cur;
        }
        cur = 0;
        for (int i = 0; i < n; i++) {
            cur += matrix[0][i];
            sum[0][i] = cur;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sum[row2][col2] - (col1 > 0 ? sum[row2][col1-1] : 0) - (row1 > 0 ? sum[row1-1][col2] : 0) + (col1 > 0 && row1 > 0 ? sum[row1-1][col1-1] : 0);
    }
}