Home » Interview coding problems/challenges

Range Sum Queries

Range Sum Queries: You are given an array of N elements, which are initially all 0. After that you will be given C commands.
Submitted by Divyansh Jaipuriyar, on September 01, 2020

Problem statement

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

Solution Approach

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:

• For the build function we the function takes 3 parameters as si segment index, ss start range for segment tree, and end range for a segment tree node.
• Then we check if we are leaf node or not, if we are at the leaf node then we update the leaf node value to the array element.
• Otherwise, we find the middle value of the index range involved in the current node and recursively build left and right half of the node, and finally update the current node value as the sum of other nodes.
• For the query function, we have five parameters as input the segment index, the range for the node, and range for query.
• But at first before return the value we first check if there are any pending updates on the lazy tree or not, if there are pending updates then we first update the lazy tree then we check other possibilities.
• For updating the lazy tree we keep in mind about the leaf nodes of the lazy tree if we reached its leaf node then we do not need to update it, otherwise we update its left half of the node and right of the node.
• Finally, in the query, we follow the same as the segment tree method of the query return process.
• In the update function, we take six values as parameters as segment index, start and end of the node of the segment tree, the query range index, and the value that will be used in updating the range.
• Also in the update function, we first check the pending update in the lazy tree if there are pending updates then we first update them

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

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

//array to store input elements.
ll arr[100001];

//segment tree array.
ll st[4 * 100001];

//lazy tree array.
ll lazy[4 * 100001];

//build function for constructing
//segment tree.
void build(ll si, ll ss, ll se)
{
    //if leaf node encounter.
    if (ss == se) {
        //store values at nodes.
        st[si] = arr[ss];
        return;
    }
    //mid index.
    ll mid = ss + (se - ss) / 2;

    //recursively build left half.
    build(2 * si, ss, mid);
    //recursively build right half.
    build(2 * si + 1, mid + 1, se);
    //update current node.
    st[si] = st[2 * si] + st[2 * si + 1];
    return;
}

//query function.
ll query(ll si, ll ss, ll se, ll qs, ll qe)
{
    //check for any pending update.
    if (lazy[si] != 0) {
        //value of lazy tree at
        //index si.
        ll dx = lazy[si];
        //make it zero since we are
        //updating it.
        lazy[si] = 0;

        //update pending updates.
        st[si] += dx * (se - ss + 1);
        //if it is not a leaf node.
        //since leaf node need no further
        //updates.
        if (ss != se) {

            // Since we are not yet updating
            //children of si we need to set
            // lazy flags for the children
            lazy[2 * si] += dx;
            lazy[2 * si + 1] += dx;
        }
    }
    //if out of range.
    if (ss > qe || se < qs)
        return 0;

    //if node is completely inside
    //query range then return node.
    if (ss >= qs and se <= qe)
        return st[si];

    //find mid index.
    ll mid = ss + (se - ss) / 2;

    // If a part of this segment overlaps with the given
    // range
    return query(2 * si, ss, mid, qs, qe) + query(2 * si + 1, mid + 1, se, qs, qe);
}

//update function.
void update(ll si, ll ss, ll se, ll qs, ll qe, ll val)
{
    //check for pending updates.
    if (lazy[si] != 0) {
        ll dx = lazy[si];
        //add pending update to current node.
        st[si] += dx * (se - ss + 1);
        //since pending is complete then
        //update it to 0.
        lazy[si] = 0;
        //check if it is not a leaf node.
        if (ss != se) {

            // Since we are not yet
            //updating children of si,
            // we need to set lazy
            //flags for the children
            lazy[2 * si] += dx;
            lazy[2 * si + 1] += dx;
        }
    }
    //if query range is out of
    //segment range.
    if (ss > qe || se < qs)
        return;

    //if segment node is completely
    //inside query range.
    if (ss >= qs and se <= qe) {
        //update current node with values.
        ll dx = (se - ss + 1) * val;
        st[si] += dx;
        //if not a leaf node.
        if (se != ss) {
            // Since we are not yet updating
            //children of si,
            // we need to set lazy flags
            //for the children
            lazy[2 * si] += val;
            lazy[2 * si + 1] += val;
        }
        return;
    }
    //find mid index.
    ll mid = ss + (se - ss) / 2;
    //recursively update left half.
    update(2 * si, ss, mid, qs, qe, val);
    //recursively update right half.
    update(2 * si + 1, mid + 1, se, qs, qe, val);

    //update current node.
    st[si] = st[2 * si] + st[2 * si + 1];
    return;
}

int main()
{
    cout << "Enter number of test cases: ";
    ll t;
    cin >> t;

    while (t--) {
        cout << "Enter N and C: ";
        ll n, c;
        cin >> n >> c;

        //initializing array with 0.
        for (ll i = 1; i <= n; i++)
            arr[i] = 0;
        //build segment tree.
        build(1, 1, n);
        ll x, y, val;
        while (c--) {
            cout << "Enter type of query: ";
            ll z;
            cin >> z;
            if (z == 0) {
                cout << "Enter range and val: ";
                cin >> x >> y >> val;
                update(1, 1, n, x, y, val);
            }
            if (z == 1) {
                cout << "Enter range: ";
                cin >> x >> y;
                cout << "Final range sum: ";
                cout << query(1, 1, n, x, y) << "\n";
            }
        }
        
        //again initializing it with 0.
        //for further operation.
        for (ll i = 1; i <= n; i++)
            arr[i] = 0;
        
        memset(lazy, 0, sizeof(lazy));
    }
    
    return 0;
}

Output

Enter number of test cases: 2
Enter N and C: 5 3
Enter type of query: 0
Enter range and val: 1 3 3
Enter type of query: 1
Enter range: 1 3
Final range sum: 9
Enter type of query: 1
Enter range: 1 5
Final range sum: 9
Enter N and C: 8 6
Enter type of query: 0
Enter range and val: 2 4 26
Enter type of query: 0
Enter range and val: 4 8 80
Enter type of query: 0
Enter range and val: 4 5 20
Enter type of query: 1
Enter range: 8 8
Final range sum: 80
Enter type of query: 0       
Enter range and val: 5 7 13
Enter type of query: 1   
Enter range: 2 5
Final range sum: 291