# 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=segmentstart index, andse=segmentend 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 andst[]as segment tree andlazy[]as our lazy tree.Time complexityfor the above approach in the worst case is:O(nlog(n))Space complexityfor the above approach in the worst case is:O(n)C++ Implementation:

need an explanation for this answer? contact us directly to get an explanation for this answerOutput: