Range Sum Query 2D — Mutable

Range Sum Query 2D — Mutable hard

Description

Implement NumMatrix:

NumMatrix(matrix) — initialize with an m × n matrix.
update(row, col, val) — set matrix[row][col] = val.
sumRegion(r1, c1, r2, c2) — sum of the sub-rectangle with corners (r1, c1) and (r2, c2).

Examples

> sumRegion(2, 1, 4, 3)   -> 8     # sum of that rectangle
  update(3, 2, 2)
  sumRegion(2, 1, 4, 3)   -> 10    # reflects the update

Constraints

1 <= m, n <= 200, many updates and queries interleaved.

Intuition — a BIT of BITs

The 1D Fenwick tree extends to 2D directly: update runs the i += i & -i loop over rows and, nested inside, over columns. prefixSum(r, c) gives the sum of the rectangle from (1,1) to (r,c). Any sub-rectangle is then the standard inclusion–exclusion of four corner prefix sums:

sumRegion(r1,c1,r2,c2) =
    pre(r2, c2) - pre(r1-1, c2) - pre(r2, c1-1) + pre(r1-1, c1-1)

Both update and query are O(log m × log n).

Code (2D Fenwick tree)

2D = “run the 1D loop in both dimensions.” Each Fenwick dimension is independent, so you simply nest the i & -i walk over rows inside the walk over columns. The four-corner inclusion–exclusion is the same identity as a 2D prefix-sum matrix — the BIT just makes it survive updates. The pattern generalizes to any number of dimensions (3D BIT = triple-nested loop).

Analysis

Time: update and sumRegion are O(log m × log n); construction O(m n log m log n).
Space: O(m n) for the BIT.

Same skin

Range Sum Query — Mutable — the 1D version this extends.
Range Sum Query 2D — Immutable — static matrix → plain 2D prefix sums, no BIT.
Inclusion–exclusion on prefix sums (Day 2) — the four-corner identity is pure 2D prefix-sum arithmetic.

Reverse Pairs My Calendar III