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

Mediumdifference-array

Range Addition

Problem (yeniden ifade)

length uzunluğunda dizi 0’dan başlar. updates[i] = [start, end, inc] kapalı aralığa inc ekler. Son diziyi döndür.

Sezgi

start’ta +inc, end+1’de -inc; önek toplam diziyi O(n)’de somutlaştırır.

Yaklaşımlar

Difference array aralık güncellemeleri

Doğrulanmadı

Zaman O(n + u)Alan O(n)

Fikir. Klasik difference array. Güncelleme başına O(n)’den kaçın.

Yürüyüş. length=5, [[1,3,2],[2,4,3],[0,2,-2]] → [-2,0,3,5,3].

Trade-off. Segment tree yalnızca güncellemelerle karışık çevrimiçi sorgular için gerekir.

Çözüm

export function getModifiedArray(length: number, updates: number[][]): number[] {
  const diff = Array(length + 1).fill(0);
  for (const u of updates) {
    diff[u[0]!] += u[2]!;
    diff[u[1]! + 1] -= u[2]!;
  }
  const res = Array(length).fill(0);
  let cur = 0;
  for (let i = 0; i < length; i++) {
    cur += diff[i]!;
    res[i] = cur;
  }
  return res;
}

export function getModifiedArray(length: number, updates: number[][]): number[] {
  const diff = Array(length + 1).fill(0);
  for (const u of updates) {
    diff[u[0]!] += u[2]!;
    diff[u[1]! + 1] -= u[2]!;
  }
  const res = Array(length).fill(0);
  let cur = 0;
  for (let i = 0; i < length; i++) {
    cur += diff[i]!;
    res[i] = cur;
  }
  return res;
}

Şablon bağlantısı

Difference array toplu aralık güncellemeleri.

Yansıma

Aralık güncellemelerini tek tek yazmak updates · n. diff[l] += v ve diff[r+1] -= v, sonra bir prefix neden yeterli?
r+1 == n olunca eksiği nereye koyarsın? Diziyi n+1 tutmazsan son hücre kaybolur mu?
Üst üste binen güncellemeler prefix’te toplanır. Boş güncelleme listesinde cevap n tane 0 mı?