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

Count of Range Sum

Problem (yeniden ifade)

i ≤ j çiftlerini say öyle ki nums[i] + … + nums[j] toplamı [lower, upper] içinde.

Sezgi

Aralık toplamı pref[j+1] - pref[i]. Yeni önek p = pref[j+1] için önceki önekler q p - upper ≤ q ≤ p - lower olmalı. Sıkıştırılmış önek değerlerinde Fenwick o aralık sayısını cevaplar, sonra p’yi ekleriz. Önekler 32-bit taşabilir; 64-bit tut.

Yaklaşımlar

Önek toplamlarında Fenwick

Doğrulanmadı

Zaman O(n log n)Alan O(n)

Fikir. pref kur. {pref, pref-lower, pref-upper} sıkıştır. Her p için sırayla: rangeSum(rank[p-upper], rank[p-lower]) sorgula, sonra update(rank[p], 1). Sorgula sonra ekle: pref[0] önce girer (boş sorgu), her pref[j+1] pref[0]…pref[j] görür.

Yürüyüş. [-2,5,-1], [lower,upper]=[-2,2]. Üç geçerli pencere: [-2], [-2,5,-1], [-1].

Trade-off. LC 315 ile aynı “sorgula sonra ekle”, elemanlar yerine önek değerlerinde. Öneklerde merge-sort böl-yönet ikizi.

Çö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 {
    if (i < 0) return 0;
    let s = 0;
    for (i++; i > 0; i -= i & -i) s += this.tree[i]!;
    return s;
  }
  rangeSum(l: number, r: number): number {
    if (r < l) return 0;
    return this.prefixSum(r) - (l > 0 ? this.prefixSum(l - 1) : 0);
  }
}

export function countRangeSum(nums: number[], lower: number, upper: number): number {
  const pref: number[] = [0];
  for (const x of nums) pref.push(pref[pref.length - 1]! + x);
  const all = new Set<number>(pref);
  for (const p of pref) {
    all.add(p - lower);
    all.add(p - upper);
  }
  const vals = [...all].sort((a, b) => a - b);
  const rank = new Map<number, number>();
  vals.forEach((v, i) => rank.set(v, i));
  const bit = new BIT(vals.length);
  let ans = 0;
  for (const p of pref) {
    const lo = rank.get(p - upper)!;
    const hi = rank.get(p - lower)!;
    ans += bit.rangeSum(lo, hi);
    bit.update(rank.get(p)!, 1);
  }
  return ans;
}

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 {
    if (i < 0) return 0;
    let s = 0;
    for (i++; i > 0; i -= i & -i) s += this.tree[i]!;
    return s;
  }
  rangeSum(l: number, r: number): number {
    if (r < l) return 0;
    return this.prefixSum(r) - (l > 0 ? this.prefixSum(l - 1) : 0);
  }
}

export function countRangeSum(nums: number[], lower: number, upper: number): number {
  const pref: number[] = [0];
  for (const x of nums) pref.push(pref[pref.length - 1]! + x);
  const all = new Set<number>(pref);
  for (const p of pref) {
    all.add(p - lower);
    all.add(p - upper);
  }
  const vals = [...all].sort((a, b) => a - b);
  const rank = new Map<number, number>();
  vals.forEach((v, i) => rank.set(v, i));
  const bit = new BIT(vals.length);
  let ans = 0;
  for (const p of pref) {
    const lo = rank.get(p - upper)!;
    const hi = rank.get(p - lower)!;
    ans += bit.rangeSum(lo, hi);
    bit.update(rank.get(p)!, 1);
  }
  return ans;
}

Şablon bağlantısı

Sıkıştırılmış anahtarlarda BIT, önekleri soldan sağa. LC 493 aynı fikir, yüklem a > 2b.

Yansıma

Aralık toplamı iki prefix’in farkı. Her prefix için p-upper ile p-lower arasında kaç eski prefix var.
Sorgula, sonra ekle. pref[0] boş sorguyla girer. Sıkıştırma negatif toplamları da sıralar.
i < j. Boş dizi 0. Tüm dizi tek aralığa düşüyorsa 1 artı iç aralıklar.