Fark Dizisi

Nasıl düşünülür

Aralıktaki her hücreyi güncellemek yerine diff dizisinde L’ye +v, R+1’e -v yaz. Tüm güncellemelerden sonra tek önek toplam değerleri yeniden kurar. Her güncelleme O(1); kurulum O(n).

Şablon şekilleri

Şekil	Temel hamle	Notlar
Aralık ekle	diff[L]+=v; diff[R+1]-=v	Sonra önek
Çoklu güncelleme	Önce tüm aralık işlemlerini topla	Tek kurulum
0-index vs 1-index	Sınırlarda tutarlı ol	R+1 = n olabilir

Karmaşıklık temeli

Aralık güncellemesi başına O(1), somutlaştırmak O(n). Diff için O(n) alan.

Şablondan probleme

1. Uzunluk n (veya temiz R+1 için n+1) diff ayır.
2. Her [L, R] += v: diff[L] += v; R+1 < n ise diff[R+1] -= v.
3. Önek: i in 1..n-1: diff[i] += diff[i-1] (veya sonuca yaz).
4. Cevapları yeniden kurulan diziden oku.

/** Difference array template: range add then prefix rebuild. */
export function applyRangeUpdates(n: number, updates: number[][]): number[] {
  const diff = new Array(n + 1).fill(0);
  for (const [l, r, val] of updates) {
    diff[l!]! += val!;
    if (r! + 1 < diff.length) diff[r! + 1]! -= val!;
  }
  const out = new Array<number>(n);
  let run = 0;
  for (let i = 0; i < n; i++) {
    run += diff[i]!;
    out[i] = run;
  }
  return out;
}

/** Difference array template: range add then prefix rebuild. */
export function applyRangeUpdates(n: number, updates: number[][]): number[] {
  const diff = new Array(n + 1).fill(0);
  for (const [l, r, val] of updates) {
    diff[l!]! += val!;
    if (r! + 1 < diff.length) diff[r! + 1]! -= val!;
  }
  const out = new Array<number>(n);
  let run = 0;
  for (let i = 0; i < n; i++) {
    run += diff[i]!;
    out[i] = run;
  }
  return out;
}