Three Ranges One Pass
An array of eight zeros, indexed 1 through 8, receives three range updates. Using a difference array d, an update that adds v to every element in [l, r] is recorded as d[l] += v and d[r + 1] -= v; the final array is the prefix sum of d.
Updates, in order:
- add 3 to
[2, 5] - add 5 to
[4, 7] - add -2 to
[1, 3]
What is the final array?
Sign in to answer questions and track your progress
Sign In