Difference Arrays
Apply many range-add updates in $O(1)$ each, then rebuild with one prefix sum.
Intermediate
Add to a[l..r]: d[l] += v; d[r+1] -= v.
Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.
Discussion (0)
Sign in or join free to ask questions and discuss this topic.