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).