Difference arrays: store changes
Picture
Add 3 to positions 1 through 3. Instead of touching three cells, record +3 where the effect begins.
Predict
Does a difference array answer arbitrary online point queries immediately?
Walk through the small example
No. A constant range addition changes only where its effect begins and ends.
Mental model and complete Python solution
Store the derivative of the array: a range update has one upward jump and one downward jump. Prefix summing integrates those changes back into final values.
What the function promises: Apply inclusive zero-based range additions to a length-n zero array. Invalid ranges raise ValueError.
def range_additions(n, updates):
difference = [0] * (n + 1)
for left, right, amount in updates:
if not 0 <= left <= right < n:
raise ValueError("Invalid range")
difference[left] += amount
difference[right + 1] -= amount
answer, running = [], 0
for i in range(n):
running += difference[i]
answer.append(running)
return answer
assert range_additions(5, [(1,3,3),(2,4,2)]) == [0,3,5,5,2]
assert range_additions(0, []) == []
Work and storage: O(u + n) time and O(n) space for u updates.
When to recognize it: A constant range addition changes only where its effect begins and ends.
Check before applying it: Online intermixed updates and queries need another structure such as Fenwick or segment tree.
Change one rule
Updates and sum queries arrive online.
See what changes
Use a Fenwick tree or segment tree, choosing based on the update and query operations.
Connect
prefix sums: A prefix sum integrates boundary changes into values.
Fenwick tree: prefix sums with updates: Support online prefix aggregates with logarithmic updates.