Difference Array : Updating a Range Query in Constant Time |  Algorithm

Difference Array : Updating a Range Query in Constant Time | Algorithm

 

Difference Array  algorithm udating range query the cs engineer



Intro :

So, recently I was solving a problem on CodeForces and I was not able to do it which is pretty common and mainly because I did not know about this algorithm and thus I read a bunch of editorials and then I found out about something called difference array and it's pretty basic and easy algorithm but makes increasing the values of a range of elements in an array a lot easier and specifically it reduces the update time from linear O(n) to constant O(1).

So, we will be learning the algorithm by understanding it first and the implementing later as I have provided the code for the implementation of the algorithm .

What do Difference Arrays do ?:

  Imagine there if the user gives a command like update(l,r,x). And the user wants that in the given array, all the elements within the position 'l' in the left to 'r' in the right, get increased by x .This algorithm updates the queries in constant time O(1). 

Naive/Simple Algorithm :

 So, by reading the question what comes into our mind first is that we will just traverse the array from l to r position most probably in a for loop and add x to all the numbers coming in the way .

But, what if the user gives a lot of queries then imagine every time going through the loop for each time we get a query is pretty tedious and we just want to do it fast. 

Now enters Difference arrays which handles each query in a constant time and at last we just traverse the array once while printing the resulting array after updating our array on a lot queries .


Time Complexity : O(1) for updating but just printing the array  takes O(n).

 The Idea :

        So, the idea of the algorithm is simply that we make a new array which stores the difference of the adjacent elements in the original array . And for each query we make a few changes in constant time that results in an updated array after all the queries are worked upon.

Understanding the algorithm :

     Let, the original provided array is denoted as - A[ ] and a query as update( l, r, x). Where l is the left position index , r the right position index and x is the number by which the elements within the given range would be increased by.   

✔️So, what do we do is we make a new array - D[ i ] the difference array which will be updated according to this- D[ i ]= A[ i ] - A[ i-1 ] , which is simply storing the difference between two adjacent elements from the original array in the difference array .

✔️And when a update query is passed we just perform these simple changes in our difference arrays : 

   D[ l ]= D[ l ] + D[ x ]  &  D[ r+1 ]= D[ r+1 ] - x  

✔️These simple above changes make the updating time constant and we do this for as many queries that we get without losing a lot of time .

✔️Now, after we perform all our updates we have to now print the resultant array and we do that by following this :

The new a value of A[ i ] = A[ i-1 ] + D[ i ]  . 

The Code :

From the Classical Algorithm Reposititory. Do give a star ! ๐ŸŒŸ                     

So, that's how in constant time we can manage to update range queries . 

Thanks, Keep Learning ๐Ÿงก