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 (restated)

Array of length length starts at 0. updates[i] = [start, end, inc] adds inc to inclusive range. Return final array.

Intuition

+inc at start, -inc at end+1; prefix sum materializes the array in O(n).

Approaches

Difference array range updates

Tested only

Time O(n + u)Space O(n)

Idea. Classic difference array. Avoid O(n) per update.

Walkthrough. length=5, [[1,3,2],[2,4,3],[0,2,-2]] → [-2,0,3,5,3].

Trade-offs. Segment tree only needed for online queries mixed with updates.

Solution

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;
}

Template connection

Difference array batch range updates.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?