Difference Arrays for Range Updates
Apply many add-on-range operations fast.
Flip the Problem
Prefix sums answered range queries fast. A difference array flips that to apply many range updates fast. 🔁
The Slow Way
Adding a value to every element in a range, repeated many times, costs O(n) per update. Across q updates that cost explodes.
All lessons in this course
- Build a Prefix Sum Array
- Sum Any Range with Subtraction
- Count Subarrays with a Target Sum
- Difference Arrays for Range Updates