Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumsegment-tree-bit

Range Sum Query 2D - Mutable

Problem (yeniden ifade)

update(row, col, val) ve sumRegion(r1, c1, r2, c2) (kapalı dikdörtgen toplamı) destekleyen 2D matris.

Sezgi

İki Fenwick iç içe: dış indeks satırlarda lowbit, iç sütunlarda. Önek (r, c), (0,0)’dan (r,c)’ye dikdörtgen toplamıdır. Inclusion-exclusion herhangi alt dikdörtgeni verir: P(r2,c2) - P(r1-1,c2) - P(r2,c1-1) + P(r1-1,c1-1).

Yaklaşımlar

2D Fenwick ağacı

Doğrulanmadı

Zaman O(log m log n)Alan O(mn)

Fikir. tree[1..m][1..n]. add i = r+1; i += i & -i ve iç içe j = c+1; j += j & -j. Önek tersi yürür. Nokta atama, saklı kopyaya göre delta.

Yürüyüş. Örnek 5×5, sumRegion(2,1,4,3)=8. update(3,2,2) sonrası aynı bölge 10.

Trade-off. LC 307 ile aynı BIT, ikinci lowbit döngüsüyle. r < 0 veya c < 0 iken önek 0 dönmeli. 2D segment tree toplam için daha ağır.

Çözüm

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)
    );
  }
}

Şablon bağlantısı

2D BIT: satır × sütun üzerinde ağaçların ağacı. LC 307 1D hal.

Yansıma

2B BIT. Hücre farkı güncellenir. Bölge dört prefix: sağ-alt eksi iki kenar artı sol-üst.
Satır ve sütun 1-index. Sınır 0 prefix 0. Tek hücre o değer.
Negatif güncelleme çalışır. Dört köşeden biri unutulursa örtüşen bölge iki kez düşer veya eksik kalır.