Skip to main content

Difference Array

Learn Difference Array (Arrays, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

What is a Difference Array? A difference array is the inverse trick of a prefix sum: it makes range updates O(1) instead of O(range length). Given diff[i] = arr[i] - arr[i-1] , to add val to every element in [l, r] : diff[l] += val diff[r + 1] -= val (if r + 1 is within bounds) After all updates are applied, take the prefix sum of diff to recover the final array - each range update was O(1), and the one final reconstruction pass is O(n).

More lessons in Arrays