Range Updates with a Difference Array
core
A difference array lets you apply many range-add updates in O(n + k) instead of O(n*k). Implement apply_updates(n, upd) where each update in upd is a triple (l, r, v) meaning "add v to every index in [l, r] inclusive" (0-indexed), and return the length-n array after all updates are applied.
Updates may overlap, be adjacent, touch either end of the array, or have l == r (a single index).
Example: apply_updates(5, {(1,3,2), (0,4,1)}) returns {1, 3, 3, 3, 1}. The first update adds 2 to indices 1..3; the second adds 1 to every index 0..4; index 0 only ever gets the second update (1), while indices 1..3 get both (2 + 1 = 3).
Tests include a case with n, k up to 2*10^5, so your solution must run in O(n + k), not O(n*k).
Input format: each test in tests/*.in is laid out as:
- Line 1: the mode letter
L. - Line 2:
n k, the array length and the number of updates. - Next
klines:l r v, one range update per line.
A performance test is instead the single line G 200000 500000 12345 (mode G): the harness builds the k updates itself from the seed and compares a checksum of apply_updates's result, so your function still receives an ordinary update list.
Test 01.in reads:
L
5 1
1 3 10
This is an array of length 5 with a single update adding 10 on the index range [1, 3].
Where you'll use it:
✦ Solution & editorial unlock with the pass.