Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumsegment-tree-bit

Range Sum Query 2D - Mutable

Problem (restated)

A 2D matrix supporting update(row, col, val) and sumRegion(r1, c1, r2, c2) (inclusive rectangle sum).

Intuition

Nest two Fenwick trees: the outer index walks rows with lowbit, the inner walks columns. Prefix (r, c) is the sum of the rectangle from (0,0) to (r,c). Inclusion-exclusion gives any sub-rectangle: P(r2,c2) - P(r1-1,c2) - P(r2,c1-1) + P(r1-1,c1-1).

Approaches

2D Fenwick tree

Unverified

Time O(log m log n)Space O(mn)

Idea. tree[1..m][1..n]. add loops i = r+1; i += i & -i and nested j = c+1; j += j & -j. Prefix walks the inverse. Point assignment is a delta against a stored copy of the matrix.

Walkthrough. The sample 5×5, sumRegion(2,1,4,3)=8. After update(3,2,2) the same region is 10.

Trade-offs. Same BIT as LC 307 with a second lowbit loop. Prefix must return 0 when r < 0 or c < 0. A 2D segment tree is heavier for sums.

Solution

export class NumMatrix {
  private m: number;
  private n: number;
  private arr: number[][];
  private tree: number[][];

  constructor(matrix: number[][]) {
    this.m = matrix.length;
    this.n = matrix[0]?.length ?? 0;
    this.arr = matrix.map((row) => row.slice());
    this.tree = Array.from({ length: this.m + 1 }, () => new Array<number>(this.n + 1).fill(0));
    for (let i = 0; i < this.m; i++)
      for (let j = 0; j < this.n; j++)
        this.add(i, j, matrix[i]![j]!);
  }

  private add(r: number, c: number, delta: number): void {
    for (let i = r + 1; i <= this.m; i += i & -i)
      for (let j = c + 1; j <= this.n; j += j & -j)
        this.tree[i]![j]! += delta;
  }

  private prefix(r: number, c: number): number {
    if (r < 0 || c < 0) return 0;
    let s = 0;
    for (let i = r + 1; i > 0; i -= i & -i)
      for (let j = c + 1; j > 0; j -= j & -j)
        s += this.tree[i]![j]!;
    return s;
  }

  update(row: number, col: number, val: number): void {
    this.add(row, col, val - this.arr[row]![col]!);
    this.arr[row]![col] = val;
  }

  sumRegion(row1: number, col1: number, row2: number, col2: number): number {
    return (
      this.prefix(row2, col2) -
      this.prefix(row1 - 1, col2) -
      this.prefix(row2, col1 - 1) +
      this.prefix(row1 - 1, col1 - 1)
    );
  }
}

export class NumMatrix {
  private m: number;
  private n: number;
  private arr: number[][];
  private tree: number[][];

  constructor(matrix: number[][]) {
    this.m = matrix.length;
    this.n = matrix[0]?.length ?? 0;
    this.arr = matrix.map((row) => row.slice());
    this.tree = Array.from({ length: this.m + 1 }, () => new Array<number>(this.n + 1).fill(0));
    for (let i = 0; i < this.m; i++)
      for (let j = 0; j < this.n; j++)
        this.add(i, j, matrix[i]![j]!);
  }

  private add(r: number, c: number, delta: number): void {
    for (let i = r + 1; i <= this.m; i += i & -i)
      for (let j = c + 1; j <= this.n; j += j & -j)
        this.tree[i]![j]! += delta;
  }

  private prefix(r: number, c: number): number {
    if (r < 0 || c < 0) return 0;
    let s = 0;
    for (let i = r + 1; i > 0; i -= i & -i)
      for (let j = c + 1; j > 0; j -= j & -j)
        s += this.tree[i]![j]!;
    return s;
  }

  update(row: number, col: number, val: number): void {
    this.add(row, col, val - this.arr[row]![col]!);
    this.arr[row]![col] = val;
  }

  sumRegion(row1: number, col1: number, row2: number, col2: number): number {
    return (
      this.prefix(row2, col2) -
      this.prefix(row1 - 1, col2) -
      this.prefix(row2, col1 - 1) +
      this.prefix(row1 - 1, col1 - 1)
    );
  }
}

Template connection

2D BIT: a tree of trees over rows × cols. LC 307 is the 1D case.

Reflection

A 2D Fenwick tree stores a cell as a delta. A rectangle is four prefixes: bottom-right, minus the two edges, plus the top-left.
Rows and columns are 1-indexed. A bound of 0 is prefix 0. One cell is that value.
A negative update is legal. Dropping one of the four corners double-counts the overlap or leaves a hole.