arujbansal's blog

By arujbansal, 4 years ago, In English

The Problem

Given $$$Q$$$ ranges of the form $$$[L_i, R_i]$$$, find for each point $$$x \in [1, N]$$$ the number of ranges that contain that point.

$$$1 \le N$$$, $$$Q \le 10^7$$$
$$$1 \le L_i \le R_i \le 10^7$$$

The Solution

One solution is to loop over each element for each range but this takes $$$O(NQ)$$$ time. We can do better.

A difference array can be used to perform multiple range update where we need to find the answer only after performing all the queries. We can do this in $$$O(N)$$$ time and space. We can update an arbitrary range in $$$O(1)$$$. It is only when we need to print our final answer that we perform an $$$O(N)$$$ computation.

Let $$$N = 5$$$. Let's create an array $$$\it{diff}$$$ of size $$$N + 2$$$ which is initially filled with zeroes.

$$$\it{diff}$$$ $$$= [0, 0, 0, 0, 0, 0, 0]$$$


Let $$$Q = 4$$$. Let's calculate the answer given these ranges — $$$[1, 3], [4, 5], [3, 4], [1, 5]$$$

Now, instead of iterating over each element of our array and adding the values, we can simply add the update 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 + 2$$$ because we subtract the update value from $$$R + 1$$$. It is possible for $$$R$$$ to be equal to $$$N$$$.

Our $$$\it{diff}$$$ array after each query:

$$$\it{diff}$$$ $$$= [0, 0, 0, 0, 0, 0, 0]$$$
$$$\it{diff}$$$ $$$= [0, 1, 0, 0, -1, 0, 0]$$$
$$$\it{diff}$$$ $$$= [0, 1, 0, 0, 0, 0, -1]$$$
$$$\it{diff}$$$ $$$= [0, 1, 0, 1, 0, -1, -1]$$$
$$$\it{diff}$$$ $$$= [0, 2, 0, 1, 0, -1, -2]$$$



Finally, we will run a loop from $$$2$$$ to $$$N$$$ (size of the array) and add $$$\it{diff}_{i - 1}$$$ to $$$\it{diff}_i$$$.

When we added our update value to index $$$L$$$ and subtracted it from index $$$R + 1$$$ and calculated prefix sums, for every range that we were supposed to increment by one, our update value got added to it. 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 to index $$$L$$$ does not get added to elements outside the update range.

We can also perform range increment queries this way. It is not necessary for us to add a fixed value of $$$1$$$ to a range. It can be any arbitrary value.

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

| Write comment?
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Some tasks in which difference array can be used

»
4 years 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 years 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 years 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 years 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 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
4 years 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 years 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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

great explanation

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

i don't see what is the relation between the problem statement and the range update code you explained

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

    Put on your glasses and you'll see it :)

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

Try this : 2014D

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

Great explaination