Range Addition medium
Description
You have an array of length n, all zeros. Apply updates, each [start, end, inc] meaning “add inc to every element in [start, end].” Return the final array after all updates.
Examples
> n = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2, 0, 3, 5, 3]
# start zeros; +2 on [1,3]; +3 on [2,4]; -2 on [0,2]Constraints
1 <= n <= 10^5,0 <= updates.length <= 10^4.
Intuition — the difference array
Applying each update element by element is O(updates × n) — too slow. The key realization: a range update only changes the array’s differences at two points. Maintain diff where diff[i] = arr[i] − arr[i−1]. Then “add inc to [start, end]” is just:
diff[start] += inc
diff[end+1] -= inc # undo it just past the rangeEach update is O(1). At the end, a single prefix sum over diff reconstructs the array in O(n). Total: O(updates + n).
Code
The difference array is “lazy propagation for the offline case.” When all updates come first and you only read the array once at the end, you don’t need a tree at all — just mark the two endpoints and integrate once. If queries were interleaved with the range updates, you’d upgrade to a lazy-propagation segment tree (or a BIT-of-differences). Recognizing “all updates, then read” vs “interleaved” tells you which tool to grab.
Analysis
- Time: O(updates + n) — each update O(1), one final O(n) sweep.
- Space: O(n) for the difference array.
Same skin
- Lazy Propagation — the online version, when reads interleave with range updates.
- Corporate Flight Bookings / Car Pooling — the exact same difference-array trick on a timeline.
- Prefix sums (Day 2) — the reconstruction step is just a prefix sum; this problem is prefix sums run in reverse.