Sign in to watch this lesson
Algorithms - Arrays · 4:23
Difference Arrays
The reverse of prefix sums: when many range updates come first and the array is read once at the end, store how each entry differs from the one before it. A range add becomes two writes, one prefix-sum sweep rebuilds the array, and on a grid four corner writes plus a 2D prefix sum do the same for rectangles. We time it against painting ranges cell by cell on a Mac and use it to find the busiest moment of a day of meetings.
You will learn
- Apply a range add in O(1) with D[l] += v and D[r+1] -= v, and rebuild the array with one prefix-sum pass
- Explain why prefix sum and difference are inverse operations, like an integral and a derivative
- Apply rectangle adds on a grid with four corner updates and a 2D prefix sum
- Use a +1/-1 sweep to count overlapping intervals, and recognise when the method needs an offline setting