Range Sum Queries
You are given an array of N elements, which are initially all 0. After that you will be given C commands. They are -
- 0 p q v - you have to add v to all numbers in the range of p to q (inclusive), where p and q are two indexes of the array.
- 1 p q - output a line containing a single integer which is the sum of all the array elements between p and q (inclusive)
Problem description:
The problem wants you to find the sum of given range [l,r] for some queries, you are also required to update not just single element but entire range for some range [a,b] with value of val as provided in the problem.
Input:
In the first line you'll be given T, number of test cases.
Each test case will start with N (N <= 100 000) and C (C <= 100 000). After that you'll be given C commands in the format as mentioned above. 1 <= p, q <= N and 1 <= v <= 10^7.
Output:
Print the answers of the queries.
Examples:
Input:
1
8 6
0 2 4 26
0 4 8 80
0 4 5 20
1 8 8
0 5 7 14
1 4 8
Output:
80
508
The problem can be solved with the help of lazy propagation and segment tree since the problem asks to update the sum of the given range for particulate query and also to return the sum for other queries.
Since here update has to be done on a range instead of a particular index so we cannot simply use a segment tree so we have to use the lazy propagation method.
Lazy propagation states that:
When there are many updates and updates are done on a range, we can postpone some updates and do those updates only when required. Here, we try to avoid recursive calls again and again.
Here we will use build, update, and query function to solve the problem.
build function will take three parameters as si=segment, index, ss=segment start index, and se=segment end index. The update function will take 5 parameters as input, 3 same as the build function parameter along with three others as us=update start index, ue=update end index, and val as the val that will be added to the given range.
The query function will take 5 parameters, 3 same as the build function along with two others as qs=query start and qe=query end.
The steps are as follows:
Here we will use arr[] as out input array and st[] as segment tree and lazy[] as our lazy tree.
Time complexity for the above approach in the worst case is: O(nlog(n))
Space complexity for the above approach in the worst case is: O(n)
C++ Implementation:
Output:
need an explanation for this answer? contact us directly to get an explanation for this answer