At first, we can see a problem:
Problem: Given an array A size of N. Initially all array elements are zero. Given Q queries, each i query is given [l, r] and x. From l to r you add x for every Ai (array elements).
example, given an array [0, 0, 0, 0, 0]. Now given l = 2, r = 4, x= 2. after operation array like this
[0, 2, 2, 2, 0].
Output print the array after performing all operations.
Constraint:
N, Q ≤ 1^9
1 ≤ l ≤ r
x ≤ 1^5
Now problems occur when we update the array in every query. Then Time complexity is O(Q*N)
That's not efficient for 1 second. Now how to solve it !?
Explain how to solve it!
.png)
for every Query add x in P array. like this:
.png)
After the end of the query, we need to calculate whole the array prefix sum.
.png)
Now, this is our final array :).
Time Complexity is O(N) and Space Complexity is O(N).
Now why does this work? We can’t believe anyone 😇. Let’s prove it.
.png)
We do this operation smartly like if we add x at l then using prefix sum we can add x to every element in the array l to r range. If r + 1 index add -x this means we are no longer adding x. More formally when we do prefix sum we add x in the position of l to r but when the index is r + 1 then x - x = 0 and from this index all element doesn’t add x.
Look at the following picture and then you can believe me :)?!
code:
.png)