Skip to main content

Difference Array (Range Query)

Learn Difference Array (Range Query) (Range Query Techniques, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Range Updates with a Difference Array A difference array is the opposite of a prefix sum, built for range updates : "add v to every element of a[l..r]". Instead of touching r-l+1 cells, change just two: diff[l] += v and diff[r+1] -= v . After all updates , a single prefix-sum pass over diff gives the final array. Each update is O(1) , the final rebuild is O(n).

More lessons in Range Query Techniques