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 - Mutable

Problem (yeniden ifade)

update(index, val) (nokta atama) ve sumRange(left, right) (kapalı aralık toplamı) destekleyen tamsayı dizisi. Karışık güncelleme/sorguda ikisi de hızlı olmalı.

Sezgi

Önek dizisi sumRange’i O(1) yapar ama update O(n). Fenwick ağacı (BIT) i’de lowbit(i) elemanlık kısmi toplam tutar; güncelleme ve önek sorgusu O(log n) ata yürür. Aralık toplamı prefix(r) - prefix(l-1). Atamayı delta yapmak için dizinin kopyasını tut.

Yaklaşımlar

Fenwick ağacı (BIT)

Doğrulanmadı

Zaman O(log n) update / queryAlan O(n)

Fikir. İçeride 1-tabanlı: i += 1, sonra güncellemede i += i & -i, önekte i -= i & -i. Kurucu her nums[i]’yi delta olarak ekler. update val - arr[i] uygular.

Yürüyüş. [1,3,5], sumRange(0,2)=9. update(1,2) delta -1. sumRange(0,2)=8.

Trade-off. BIT, tersinir aralık toplamları için şablon. Segment tree de çalışır, min/max’a uzanır. Ağacı 0-indeksleme; lowbit 0’daki boş yuvaya ihtiyaç duyar.

Çözüm

class BIT {
  private n: number;
  private tree: number[];
  constructor(n: number) {
    this.n = n;
    this.tree = new Array<number>(n + 1).fill(0);
  }
  update(i: number, delta: number): void {
    for (i++; i <= this.n; i += i & -i) this.tree[i]! += delta;
  }
  prefixSum(i: number): number {
    let s = 0;
    for (i++; i > 0; i -= i & -i) s += this.tree[i]!;
    return s;
  }
  rangeSum(l: number, r: number): number {
    return this.prefixSum(r) - (l > 0 ? this.prefixSum(l - 1) : 0);
  }
}

export class NumArray {
  private arr: number[];
  private bit: BIT;
  constructor(nums: number[]) {
    this.arr = nums.slice();
    this.bit = new BIT(nums.length);
    for (let i = 0; i < nums.length; i++) this.bit.update(i, nums[i]!);
  }
  update(index: number, val: number): void {
    this.bit.update(index, val - this.arr[index]!);
    this.arr[index] = val;
  }
  sumRange(left: number, right: number): number {
    return this.bit.rangeSum(left, right);
  }
}

class BIT {
  private n: number;
  private tree: number[];
  constructor(n: number) {
    this.n = n;
    this.tree = new Array<number>(n + 1).fill(0);
  }
  update(i: number, delta: number): void {
    for (i++; i <= this.n; i += i & -i) this.tree[i]! += delta;
  }
  prefixSum(i: number): number {
    let s = 0;
    for (i++; i > 0; i -= i & -i) s += this.tree[i]!;
    return s;
  }
  rangeSum(l: number, r: number): number {
    return this.prefixSum(r) - (l > 0 ? this.prefixSum(l - 1) : 0);
  }
}

export class NumArray {
  private arr: number[];
  private bit: BIT;
  constructor(nums: number[]) {
    this.arr = nums.slice();
    this.bit = new BIT(nums.length);
    for (let i = 0; i < nums.length; i++) this.bit.update(i, nums[i]!);
  }
  update(index: number, val: number): void {
    this.bit.update(index, val - this.arr[index]!);
    this.arr[index] = val;
  }
  sumRange(left: number, right: number): number {
    return this.bit.rangeSum(left, right);
  }
}

Şablon bağlantısı

BIT nokta-güncelleme / aralık-toplam. LC 303 değişmez önek kuzeni; LC 308 bunun 2D hali.

Yansıma

BIT 1-index. Güncelleme farkı ekler, aralık iki prefix’in farkı. İkisi de O(log n).
İlk dizi kurulumda yapraklara yazılır. Sol sınır 0 ise prefix 0.
Negatif fark çalışır. Düz dizi her sorguda aralığı baştan tarar.