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

Easyprefix-sum

Range Sum Query. Immutable

Problem (yeniden ifade)

Değişmez nums verilen, sumRange(left, right) sorularını verimli yanıtlayan bir yapı tasarla.

Sezgi

prefix[i] = ilk i elemanın toplamı; aralık = prefix[r+1]-prefix[l].

Yaklaşımlar

Önek toplamlar

Doğrulanmadı

Zaman O(1) queryAlan O(n)

Fikir. Öneki bir kez kur; her sorgu iki dizi erişimi.

Adım adım. nums=[-2,0,3,-5,2,-1]; sumRange(0,2)=1; sumRange(2,5)=-1.

Trade-off’lar. Yalnızca değişmez + aralık-toplamı için segment tree abartı.

Çözüm

export class NumArray {
  private pref: number[];
  constructor(nums: number[]) {
    this.pref = new Array(nums.length + 1).fill(0);
    for (let i = 0; i < nums.length; i++) this.pref[i + 1] = this.pref[i]! + nums[i]!;
  }
  sumRange(left: number, right: number): number {
    return this.pref[right + 1]! - this.pref[left]!;
  }
}

export class NumArray {
  private pref: number[];
  constructor(nums: number[]) {
    this.pref = new Array(nums.length + 1).fill(0);
    for (let i = 0; i < nums.length; i++) this.pref[i + 1] = this.pref[i]! + nums[i]!;
  }
  sumRange(left: number, right: number): number {
    return this.pref[right + 1]! - this.pref[left]!;
  }
}

Şablon bağlantısı

Değişmez önek toplamları: sumRange = prefix[r+1] − prefix[l]. Değişken kuzeni Fenwick (LC 307).

Yansıma

Değişmez dizi + çok sorgu → önek toplam. sum(l..r) = pref[r+1] - pref[l]. pref[0] = 0 tohumu neden?
Inclusive right off-by-one’ı: pref[right+1].
Güncellenebilir olsaydı (307) neden BIT/segment tree?