Prefix Sum and Difference Array
Four prompts on prefix sums for range queries and difference arrays for range updates. Includes one trace and one bug hunt.
1,074 views
9
Implement rangeSum(arr, queries) where each query is [l, r] (inclusive). Return an array of answers using a prefix-sum table so that each query is answered in O(1).
Examples
Example 1:
Input: arr = [1, 2, 3, 4, 5], queries = [[0, 2], [1, 3], [2, 4]]
Output: [6, 9, 12]
Explanation: prefix = [0, 1, 3, 6, 10, 15]. Each query [l, r] returns prefix[r + 1] - prefix[l]: 6 - 0 = 6, 10 - 1 = 9, 15 - 3 = 12. Construction is O(n) and each query is O(1).function rangeSum(arr, queries) {
// TODO: precompute prefix, then answer each query in O(1)
}Implement applyRangeUpdates(n, updates) where each update is [l, r, delta] adding delta to every index in [l, r]. Use a difference array so applying all updates is O(n + u).
Examples
Example 1:
Input: n = 5, updates = [[1, 3, 2], [0, 2, 1]]
Output: [1, 3, 3, 2, 0]
Explanation: diff after the two updates is [1, 2, 0, -2, -1, 0]. Prefix sum yields [1, 3, 3, 1, 0]. Wait, recompute: diff = [+1 at 0, +2 at 1, +1 at 2 net, -2 at 3 net, ...]. Final values are [1, 3, 3, 2, 0]. Each update is O(1) and the final sweep is O(n), beating O(n * u) naive.function applyRangeUpdates(n, updates) {
// TODO: build diff array, then prefix-sum to recover final values
}Trace it. Given arr = [3, 1, 4, 1, 5, 9, 2], what is the prefix-sum array (with leading 0) and what is the answer to the range sum [2, 5] inclusive?
Spot the bug. This apply is meant to compute arr after a single range update [l, r, delta] using a difference-array idea, but it produces wrong values for r = arr.length - 1.
Examples
Example 1:
Input: apply([0, 0, 0, 0, 0], 1, 4, 5)
Output (buggy version): [0, 5, 5, 5, 0]
Output (fixed version): [0, 5, 5, 5, 5]
Explanation: The decrement must land at r + 1, not r. Writing diff[r] -= delta cancels the update at index r itself, dropping the right end of the range. Sizing diff as n + 1 and using diff[r + 1] -= delta fixes it.function apply(arr, l, r, delta) {
const n = arr.length;
const diff = new Array(n).fill(0);
diff[l] += delta;
diff[r] -= delta;
let running = 0;
for (let i = 0; i < n; i++) {
running += diff[i];
arr[i] += running;
}
return arr;
}