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
great 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
Put on your glasses and you'll see it :)
Try this : 2014D
Great explaination