Prefix Sums and Difference Arrays

// Template 1: running sums. prefix[i] is the sum of the first i values (prefix[0] = 0), so
// sum(nums[l..r]) = prefix[r + 1] - prefix[l] for any range, in O(1) after an O(n) build.
export function buildPrefix(nums) {
  const prefix = new Array(nums.length + 1).fill(0);
  for (let i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] + nums[i];
  return prefix;
}

export function rangeSum(prefix, left, right) {
  return prefix[right + 1] - prefix[left];   // inclusive on both ends
}

// Template 2: prefix sum + hash map. sum(nums[i+1..j]) = P(j) - P(i), so a subarray ending at j sums to k
// exactly when an EARLIER prefix equals P(j) - k. Works with negative numbers, unlike a sliding window.
// Longest version: remember the FIRST index of each prefix sum (earliest start = longest subarray).
export function longestSubarrayWithSum(nums, k) {
  const firstIndex = new Map([[0, -1]]);   // the empty prefix, "before index 0"
  let sum = 0;
  let best = 0;
  for (let j = 0; j < nums.length; j++) {
    sum += nums[j];
    if (firstIndex.has(sum - k)) best = Math.max(best, j - firstIndex.get(sum - k));
    if (!firstIndex.has(sum)) firstIndex.set(sum, j);   // never overwrite: keep the earliest
  }
  return best;
}

// Template 3: 2D prefix sums. P[r][c] is the sum of the rectangle grid[0..r-1][0..c-1] (one extra row and
// column of zeros), so any rectangle sum is four lookups by inclusion-exclusion.
export function buildPrefix2D(grid) {
  const rows = grid.length;
  const cols = rows ? grid[0].length : 0;
  const P = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0));
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      P[r + 1][c + 1] = grid[r][c] + P[r][c + 1] + P[r + 1][c] - P[r][c];   // the overlap was added twice
    }
  }
  return P;
}

// Sum of grid[r1..r2][c1..c2], all ends inclusive.
export function rectSum(P, r1, c1, r2, c2) {
  return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1];
}

// Template 4: difference array. To add `delta` to every index in [left, right], write +delta at left and
// -delta at right + 1: O(1) per update. One running sum at the end turns the differences into values.
export function applyRangeAdds(n, updates) {
  const diff = new Array(n + 1).fill(0);   // one spare slot so right + 1 never falls off
  for (const [left, right, delta] of updates) {
    diff[left] += delta;
    diff[right + 1] -= delta;
  }
  const out = new Array(n);
  let running = 0;
  for (let i = 0; i < n; i++) {
    running += diff[i];
    out[i] = running;
  }
  return out;
}