Difference Array

How to think about it

Instead of updating every cell in a range, write +v at L and -v at R+1 on a diff array. After all updates, a single prefix sum rebuilds the values. Each update is O(1); rebuild is O(n).

Template shapes

Shape	Core move	Notes
Range add	diff[L]+=v; diff[R+1]-=v	Then prefix
Multiple updates	Batch all range ops first	One rebuild
0-index vs 1-index	Be consistent on bounds	R+1 may be n

Complexity baseline

O(1) per range update, O(n) to materialize. Space O(n) for the diff array.

From template to problem

1. Allocate diff of length n (or n+1 if you need a clean R+1 slot).
2. For each update [L, R] += v: diff[L] += v; if R+1 < n: diff[R+1] -= v.
3. Prefix: for i in 1..n-1: diff[i] += diff[i-1] (or write into result).
4. Read answers from the rebuilt array.

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