[LintCode] Problem 817 - Range Sum Query 2D - Mutable

Posted on | In ,

Given a 2D matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2). And the elements of the matrix could be changed.

You have to implement three functions:

  • NumMatrix(matrix) The constructor.
  • sumRegion(row1, col1, row2, col2) Return the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
  • update(row, col, val) Update the element at (row, col) to val.

Note

  1. The matrix is only modifiable by update.
  2. You may assume the number of calls to update and sumRegion function is distributed evenly.
  3. You may assume that row1 ≤ row2 and col1 ≤ col2.

Example

No.1

Input:

1
2
3
4
5
6
7
NumMatrix(
    [[3,0,1,4,2],
    [5,6,3,2,1],
    [1,2,0,1,5],
    [4,1,0,1,7],
    [1,0,3,0,5]]
)

sumRegion(2,1,4,3)
update(3,2,2)
sumRegion(2,1,4,3)

Output:
8
10

No.2

Input:
NumMatrix([[1]])
sumRegion(0, 0, 0, 0)
update(0, 0, -1)
sumRegion(0, 0, 0, 0)

Output:
1
-1

Code

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class BinaryIndexedTree {
    private int[][] sum;

    public BinaryIndexedTree(int m, int n) {
        sum = new int[m + 1][n + 1];
    }

    public void update(int row, int col, int delta) {
        for (int i = row; i < sum.length; i += lowbit(i)) {
            for (int j = col; j < sum[0].length; j += lowbit(j))
                sum[i][j] += delta;
        }
    }

    public int query(int row, int col) {
        int result = 0;

        for (int i = row; i > 0; i -= lowbit(i)) {
            for (int j = col; j > 0; j -= lowbit(j))
                result += sum[i][j];
        }

        return result;
    }

    private int lowbit(int x) {
        return x & (-x);
    }
}

private BinaryIndexedTree tree;
private int[][] matrix;

public NumMatrix(int[][] matrix) {
    this.matrix = matrix;
    int m = matrix.length;
    int n = matrix[0].length;
    tree = new BinaryIndexedTree(m, n);

    for (int i = 0; i < m; i++) {   
        for (int j = 0; j < n; j++)
            tree.update(i + 1, j + 1, matrix[i][j]);
    }
}

public void update(int row, int col, int val) {
    tree.update(row + 1, col + 1, val - matrix[row][col]);
    matrix[row][col] = val;
}

public int sumRegion(int row1, int col1, int row2, int col2) {
    return tree.query(row2 + 1, col2 + 1) + tree.query(row1, col1)
            - tree.query(row1, col2 + 1) - tree.query(row2 + 1, col1); 
}