Difference Array
1 problems · 1 with full explanations
0 Easy1 Medium0 Hard
A difference array enables range increment updates in O(1): diff[l] += v, diff[r+1] -= v. Reconstruct the original array with a prefix sum. Use for event sweep problems, overlapping intervals, and paint-range queries. 2D extension handles matrix range updates.
How to practice
To practice Difference Array problems effectively, start with the Easy problems listed below, trace through each solution on paper, then re-implement without looking. When you can recognise the difference array pattern within 30 seconds of reading a new problem, move on to Medium difficulty. Use the related topic pages and our study guide for a structured progression.