### arujbansal's blog

By arujbansal, 3 years ago,

# 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 :)

• +101

| Write comment?
 » 3 years ago, # |   +1 Some tasks in which difference array can be used
 » 3 years ago, # |   +2
 » 3 years ago, # |   +1 "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$.
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 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).
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +1 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.
•  » » » » 3 years ago, # ^ |   0 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).
•  » » » » » 7 months ago, # ^ |   -7 What is BIT?
•  » » » » » » 7 months ago, # ^ |   0 Binary Indexed Tree/Fenwick Tree
•  » » » » » » » 7 months ago, # ^ |   0 Ok
•  » » » » » » » 5 months ago, # ^ |   0 can you kindly write your code with an explanation ... so that we all can read
 » 3 years ago, # |   0
 » 2 years ago, # |   0 How about a difference array based problem implemented on 2-d array?Implementation: https://www.codechef.com/viewsolution/36993763
 » 2 years ago, # | ← Rev. 3 →   0 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
 » 7 months ago, # |   0 great explanation