Difference Array Technique

Consider an array A[] of integers and following query -

update(l, r, x) : Adds x to all values from A[l] to A[r] (both inclusive).

A simple solution is to do following :

Run a loop from l to r and add x to all elements from A[l] to A[r]

Time complexities of both of the above operations is O(n). An efficient solution is to use difference array.

Difference array D[i] of a given array A[i] is defined as D[i] = A[i]-A[i-1] (for 0 < i < N ) and D[0] = A[0] considering 0 based indexing. Difference array can be used to perform range update queries “l r x” where l is left index, r is right index and x is value to be added and after all queries you can return original array from it. Where update range operations can be performed in O(1) complexity.

Add x to D[l] and subtract it from D[r+1], i.e., we do D[l] += x, D[r+1] -= x

Time complexity of update here is improved to O(1).

Reference : https://www.geeksforgeeks.org/difference-array-range-update-query-o1/