Difference Array
Record range updates as two endpoint deltas. A final prefix sum applies them all.
Difference Array: Three overlapping ranges
Update 1: add 5 to indices 1 to 3. Two writes: +5 at 1, where it starts, and -5 at 4, where it stops. The 2 cells between them are never touched.
Cost
- Best
- O(n + q)
- Average
- O(n + q)
- Worst
- O(n + q)
- Space
- O(n)
O(1) per range update one O(n) finalization.
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
Difference Array covers these too, in the same run.