Difference Arrays: The Inverse of Prefix Sums

Concepts: pyDifferenceArray, pyRangeUpdate, pyBulkUpdate

If prefix sums let you query ranges efficiently, difference arrays let you update ranges efficiently. The duality is perfect and deliberate. With a prefix sum array, you precompute cumulative sums and query any range in O(1). With a difference array, you apply range updates in O(1) and reconstruct the final array in O(n) with a prefix sum pass. They are inverses of each other. The difference array is underrated in interviews -- most candidates have never heard of it, which means knowing it immediately sets you apart. The Difference Array Technique The difference array diff[] is defined as: diff[0] = arr[0], diff[i] = arr[i] - arr[i-1] for i > 0. The original array is the prefix sum of diff. Applying a range update 'add V to all elements from index L to R' translates to exactly two operatio