Least You Need to Know: Difference Arrays, Boundary Marking, and Range Updates
Open lesson
Difference arrays invert the prefix-sum idea: instead of storing cumulative totals directly, they store where changes begin and end. After marking update boundaries, one prefix sweep reconstructs the final values.