215. Range Sum Query 2D - Mutable

Extend the 1-D Fenwick idea to two dimensions: each tree cell stores the sum of a sub-rectangle. A point update and a prefix-rectangle query each touch O(log m · log n) nodes; a rectangle sum is four prefix queries by inclusion-exclusion.

2D BIT

A tree[i][j] accumulates sums over a rectangle whose height and width are the lowest set bits of i and j. Both operations nest the 1-D BIT loop:

add(r, c, delta):
    i = r+1
    while i <= m:
        j = c+1
        while j <= n: tree[i][j] += delta; j += j & -j
        i += i & -i

query(r, c):        # sum of the top-left r x c block
    s = 0; i = r
    while i > 0:
        j = c
        while j > 0: s += tree[i][j]; j -= j & -j
        i -= i & -i
    return s

• update(row, col, val): apply delta = val - current then store current.
• sumRegion(r1,c1,r2,c2) = query(r2+1,c2+1) - query(r1,c2+1) - query(r2+1,c1) + query(r1,c1) (inclusion-exclusion of four prefix rectangles).

Worked example

For the 5×5 matrix in the examples, sumRegion(2,1,4,3) = 8; after update(3,2,2) the same region becomes 10.

Complexity

• Time: O(log m · log n) per update and per query.
• Space: O(m·n).

import java.util.*;

class NumMatrix {
    private int R, C;
    private int[][] mat;
    private int[][] tree;

    public NumMatrix(int[][] matrix) {
        R = matrix.length;
        C = R > 0 ? matrix[0].length : 0;
        mat = new int[R][C];
        tree = new int[R + 1][C + 1];
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                update(r, c, matrix[r][c]);
            }
        }
    }

    private void add(int r, int c, int delta) {
        for (int i = r + 1; i <= R; i += i & (-i)) {
            for (int j = c + 1; j <= C; j += j & (-j)) {
                tree[i][j] += delta;
            }
        }
    }

    private int query(int r, int c) {  // sum of the top-left r x c block
        int s = 0;
        for (int i = r; i > 0; i -= i & (-i)) {
            for (int j = c; j > 0; j -= j & (-j)) {
                s += tree[i][j];
            }
        }
        return s;
    }

    public void update(int row, int col, int val) {
        int delta = val - mat[row][col];
        mat[row][col] = val;
        add(row, col, delta);
    }

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