Question Bank
Prefix Sum and Difference Array
Difficulty: Medium
Four prompts on prefix sums for range queries and difference arrays for range updates. Includes one trace and one bug hunt.
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,072 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).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.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.