# 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.

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:

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

Some tasks in which difference array can be used

602B - Approximating a Constant Range

"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$$$.

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).

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

Like, suppose your difference array looks something like

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.

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).

What is BIT?

Binary Indexed Tree/Fenwick Tree

.

AtCoder ARC C-Lamps

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

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

It can also be done in O(n^3). Here is the solution. solution

great explanation

very nice explanation.

https://mirror.codeforces.com/contest/1864/problem/D

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