AlgoScope

Difference Array

Record range updates as two endpoint deltas. A final prefix sum applies them all.

Array algorithms and techniques, algorithm, intermediate
Add 5 to indices 1 through 3 by writing +5 at slot 1 and -5 at slot 4.active 1-300510203-5405060708
Add 5 to indices 1 through 3 by writing +5 at slot 1 and -5 at slot 4.active 1-300510203-5405060708

Difference Array: Three overlapping ranges

Decision, step 2 of 14

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.

Leads to

Topics that need this one first.

Taught by the same lesson

Difference Array covers these too, in the same run.