arujbansal's blog

By arujbansal, 4 months ago, In English

The generalised use case for a difference array is this:
You are given Q ranges in the form (L, R) and for each point you have to find how many ranges overlap at that point.

In this problem, we are given an array and M operations in the form (L, R, Value) and for each operation, we have to add Value to each point in the range L, R of the given array. After this, we are given K queries in the form of (x, y) and for each point in the range (x, y), we have to perform operations x1, x2 ... y.

Before we get started, if you are not familiar with prefix sums, I would suggest you read up on it here:
GFG Prefix Sums

Difference Arrays are basically used to perform multiple range update queries where we only need to find the answer after performing all the queries. They allow us to do so in O(n).
Note: Performing a single update query is O(1). It is only when we need to print our final answer, we use prefix sums which take O(n).

Let's say I have the following array of 5 integers called elements (1 based indexing):
1 1 1 1 1

l is the left boundary of our range query and r is the right boundary of our query.
My queries are as follows (in the format l, r, and update value):
1 3 2
4 5 3
1 4 1
1 5 -1

Let's assume that our constraints are pretty large and we need a very efficient solution to this problem.
Instead of iterating over the range and adding the value to each element in our array, we will create a new array (the difference array) called diff initially filled with zeroes. It will be of size 1 + the size of our initial array.
Now, instead of iterating over each element of our array and adding the values, we can simply add the value to index l of our difference array and subtract it from the index r+1 of our difference array. We need a difference array of size n+1 because we subtract the update value from r+1. Here, the right bound of the query + 1 can also the number present at position n+1.
We will see how this works in a moment.

Difference Array at each query:
0 0 0 0 0 0 (Before any query)
2 0 0 -2 0 0
2 0 0 1 0 -3
3 0 0 1 -1 -3
2 0 0 1 -1 -2

Finally, we will run a loop from 2 to n (size of the array) and add diff[i-1] to diff[i].
Now, running a loop from 1 to n, we will add diff[i] to elements[i].

What are we doing?
When we added our update value to index l and subtracted it from index r+1 and later on used prefix sums, for every range that we were supposed to update, our update value got added to it. As we were running the loop from 1 to n only once, we subtracted the update value from index r+1 of the difference array so that when we are summing it up, the update value we added earlier to index l does not get added to elements outside the update range.

Let's say we had a difference array of 0's as follows:
0 0 0 0 0 0

If we had to update range 2 — 4 with value 2, we would add 2 to index 2 and subtract 2 from index 5:
0 2 0 0 -2 0

Now when we use prefix sums, our final array will look like this:
0 2 2 2 0 0

If we had not subtracted 2 from r+1, our array would look like: 0 2 2 2 2 2



Code:
#include <bits/stdc++.h>

using namespace std;

int main() {

	int n = 5; // Size of array
	vector<int> elements{0, 1, 1, 1, 1, 1}; // 1 based indexing
        // n+2 because we need are not using the 0-th index and we need one more element in the array.
	vector<int> diff(n + 2, 0); 
	
	int updateValue = 10;
	int l = 2, r = 5;
	diff[l] += updateValue;
	diff[r + 1] -= updateValue;
	
	for (int i = 1; i <= n; i++) {
		diff[i] += diff[i - 1];
		elements[i] += diff[i];
	}
	for (int i = 1; i <= n; i++) cout << elements[i] << " ";
	return 0;
}

I highly recommend you try this problem based on this concept to understand it better:
295A - Greg and Array
My solution:
83554391

Feel free to share problems :)

 
 
 
 
  • Vote: I like it
  • +101
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Some tasks in which difference array can be used

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

"perform multiple range update queries where we only need to find the answer after performing all the queries"

You can use a BIT to take away this restriction with the trade-off of a program being $$$O(QlogN)$$$ instead of $$$O(N + Q)$$$

The idea is exactly the same, but since the BIT has the property that query(x) gives you (in this case) the sum of all elements from positions $$$1..N$$$.

  • »
    »
    4 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Yeah BITs can also be used here, I'll add that to the post :)
    If I'm not wrong, we can query twice to answer for a range (L, R).

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      I mean you could but it doesn't really make much sense in this scenario.

      Like, suppose your difference array looks something like

      1 1 0 0 2 -1 -2 0 -1
      

      What does it mean to query $$$[3,$$$ $$$6]$$$?

      Using a BIT allows you to skip the "calculate the prefix sums" step since a BIT already calculates prefix sums by definition.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I meant that we can query our BIT twice to get the sum for a range (L, R) instead of a single query for (0, R).

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I really wanted to write a blog on this concept as I was completely shocked by this trick when I solved this problem:
D. Constant Palindrome Sum.
You have done a great job!!

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How about a difference array based problem implemented on 2-d array?

Here it is: https://www.codechef.com/CENS2020/problems/CENS20A

Implementation: https://www.codechef.com/viewsolution/36993763

»
4 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

wrong solution for geeks for geeks question

But it's correct solution in O(n*2^n), using difference array and some complex maths,here