Range in range sum with point update

Question

We are given an array A with N elements and also N ranges, each of the form [L, R]. Call the value of a range the sum of all the elements in A from index L to index R, inclusive.

Example : Let Array A = [2 5 7 9 8] and a range given is [2,4] then value of this range is 5+7+9=21

Now we are given Q queries each query of one of the 2 types:

1. 0 X Y : It means change Xth element of array to Y.
2. 1 A B : It means we need to report the sum of values of ranges from A to B.

Example : Let array A = [2 3 7 8 6 5] and let we have 3 ranges :

R1: [1,3] Then value corresponding to this range is 2+3+7=12
R2: [4,5] Then value corresponding to this range is 8+6=14
R3: [3,6] Then value corresponding to this range is 7+8+6+5=26

Now let we have 3 queries:

Q1: 1 1 2
Then here answer is value of Range1 + value of Range2 = 12+14=26 

Q2: 0 2 5
It means Change 2nd element to 5 from 3.It will change the result of Range 1.
Now value of Range1 becomes 2+5+7=14

Q3: 1 1 2
Then here answer is value of Range1 + value of Range2 = 14+14=28 

How to do it if we have 10^5 Queries and N is also upto 10^5. How to report to Queries2 in an efficient way ?

My Approach : The first query can be handled easily. I can build a segment tree from the array. I can use it to calculate the sum of an interval in the first array (an element in the second array). But how can i handle the second query in O(log n)? In the worst case, the element I update will be in all the intervals in the second array.

I need a O(Qlog N) or O(Q(logN)^2) solution.

Obviously we cant have a O(N) for each query.So please help to get efficient way

My Current Code :

#include<bits/stdc++.h>
using namespace std;
long long  arr[100002],i,n,Li[100002],Ri[100002],q,j;
long long  queries[100002][2],query_val[100002],F[100002],temp;
long long   ans[100002];
int main()
{
scanf("%lld",&n);
for(i=1;i<=n;i++)
    scanf("%lld",&arr[i]);
for(i=1;i<=n;i++)
{
    scanf("%lld%lld",&Li[i],&Ri[i]);
}
for(i=1;i<=n;i++)
{
    F[n] = 0;
    ans[i] = 0;
}
scanf("%lld",&q);
for(i=1;i<=q;i++)
{
    scanf("%lld",&query_val[i]);
    scanf("%lld%lld",&queries[i][0],&queries[i][1]);
}
for(i=1;i<=n;i++)
{
    for(j=Li[i];j<=Ri[i];j++)
    {
        F[i] = F[i] + arr[j];
    }
}
long long  diff;
long long  ans_count = 0,k=1;
for(i=1;i<=q;i++)
{
    if(query_val[i] == 1)
    {
        temp = arr[queries[i][0]];
        arr[queries[i][0]] = queries[i][1];
        diff =  arr[queries[i][0]] - temp;
        for(j=1;j<=n;j++)
        {
            if(queries[i][0]>=Li[j] && queries[i][0]<=Ri[j])
                F[j] = F[j] + diff;
            ++k;
        }

    }
    else if(query_val[i] == 2)
    {
        ++ans_count;
        for(j=queries[i][0];j<=queries[i][1];j++)
            ans[ans_count] = ans[ans_count] + F[j];

    }
}
for(i=1;i<=ans_count;i++)
{
    printf("%lld\n",ans[i]);
}
return 0;
}

Though the code is correct but for larger test cases it take huge time.Please help

Answer 1

You could use Segment Tree. http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

#include <cstdio>

const int MAX_N = 1000003;

int tree[(1 << 21) + 3], a[MAX_N], N, M;
int x, y;

int query(int n, int l, int r) {
    if(l > y || r < x) {
        return 0;
    }
    if(l >= x && r <= y) {
        return tree[n];
    }
    int q = query(2*n, l, (l + r)/2);
    int p = query(2*n + 1, (l + r)/2 + 1, r);
    return p + q;
}

void init(int n, int l, int r) {
    if(l == r) {
        tree[n] = a[l];
        return;
    }
    init(2*n, l, (l + r)/2);
    init(2*n + 1, (l + r)/2 + 1, r);
    tree[n] = tree[2*n] + tree[2*n + 1];
}

void update(int n, int l, int r) {
    if(l > y || r < x)
        return;
    if(l == r && x == r) {
        tree[n] = y;
        return;
    }
    else if(l == r) {
        return;
    }
    update(2*n, l, (l + r)/2);
    update(2*n + 1, (l + r)/2 + 1, r);
    tree[n] = tree[2*n] + tree[2*n + 1];
}
int main() {
    scanf("%d%d", &N, &M);
    for(int i = 0; i < N; i++) {
        scanf("%d", &a[i]);
    }
    init(1, 0, N - 1);
    for(int i = 0; i < M; i++) {
        int c;
        scanf("%d%d%d", &c, &x, &y);
        if(!c) {
            a[x] = y;
            update(1, 0, N - 1);
        } else {
            printf("%d\n", query(1, 0, N - 1));
        }
    }
    return 0;
}

Basic idea is to extend your array of elements into a binary tree. Every node of that tree holds information about sum of the elements of its children. And you can easily know which range is some node covering by applying this trick:

Root is holding information of range [1,N]. Left child of the root is holding information about range [1, int(N/2)]. Right child of the root is holding information about range [int(N/2)+1, N].

In general if node 'A' is holding information about range [l, r]. Then left child holds information about range [l, int((l+r)/2)] and right child is holding information about range [int((l+r)/2)+1, r].

There is also a good trick to represent binary tree in array. Lets say that you hold your tree in array 'tree' (as I am doing I my code). Then root of that tree will be in tree[1]. Left child of the root is going to be tree[2] and right child of tree root is going to be tree[3].

In general if you are on the node n then its left child is 2*n and right child is 2*n + 1.

That is why I am calling my query and update function with (1, 0, N - 1). I start with the root node 1. And range that I am covering with that node i [0, N-1]. And I am always trying to find first node what fits in the range that I need to calculate the sum of.

That's a start. Try googling more about Segment Trees. When you start exploring you will see that there is a couple of ways you can represent your tree.

Good luck. :)

Answer 2

#include <iostream>
using namespace std;
typedef long long ll;
void updateSegementLazyTree(ll *tree , ll *lazy , ll low, ll high,ll startR ,ll endR ,ll updateValue ,ll treeNode)
{

    //before using current node we need to check weather currentnode has any painding updation or not
    if (lazy[treeNode]!=0)
    {
        //update painding updation
        tree[treeNode]  +=  (high-low+1)*lazy[treeNode];
        //transfer update record to child of current node if child possible
        if (low!=high)
        {
            //that's means child possible
            lazy[treeNode*2]    += lazy[treeNode];  //append update to left child
            lazy[treeNode*2+1]  += lazy[treeNode];  //append update to right child
        }
        lazy[treeNode]=0;//remove lazyness of current node
    }
    //if our current interval [low,high] is completely outside of the given Interval[startR,endR]
    if (startR >high || endR <low || low>high)
    {   
        //then we have to ignore those path of tree
        return;
    }
    //if our current interval is completely inside of given interval
    if (low >=startR && high <=endR)
    {
        //first need to update the current node with their painding updation
        tree[treeNode]  += (high-low+1)*updateValue;
        if (low!=high)
        {
            //that's means we are at the non-leaf node
            lazy[treeNode*2] +=updateValue; //so append lazyness to their left child
            lazy[treeNode*2+1] +=updateValue;//append lazyness to their right child
        }
        return;
    }
    //partially inside and outside then we have to traverse all sub tree i.e. right subtree and left subtree also
    ll mid=(low+high)/2;
    updateSegementLazyTree(tree ,  lazy ,  low,  mid, startR , endR , updateValue , treeNode*2);
    updateSegementLazyTree(tree ,  lazy ,  mid+1,  high, startR , endR , updateValue , treeNode*2+1);

    //while poping the function from stack ,we are going to save what i have done....Ok!!!!
    //update tree node:-
    tree[treeNode]  = tree[treeNode*2] + tree[treeNode*2+1];    //left sum+rightsum(after updation)
}
ll getAnswer(ll *tree ,ll * lazy , ll low, ll high ,ll startR,ll endR , ll treeNode)
{
    //base case
    if (low>high)
    {
        return 0;
    }
    //completely outside
    if (low >endR || high <startR)
    {
        return 0;
    }
    //before using current node we need to check weather currentnode has any painding updation or not
    if (lazy[treeNode]!=0)
        {
            //i.e. if we would have added x value from low to high then total changes for root node will be (high-low+1)*x
            tree[treeNode]  += (high-low+1)*lazy[treeNode];
            if (low!=high)
            {
                //if we are at non-leaf node
                lazy[treeNode*2] += lazy[treeNode]; //append updateion process to left tree
                lazy[treeNode*2+1] += lazy[treeNode];//append updation process to right tree
            }
            lazy[treeNode]=0;
        }
    //if our current interval is completely inside of given interval
    if (low >=startR && high <=endR)
    {
        return tree[treeNode];
    }
    //if our current interval is cpartially inside and partially out side of given interval then we need to travers both side left and right too
    ll mid=(low+high)/2;
    if(startR>mid)
    {
        //that's means our start is away from mid so we need to treverse in right subtree
        return getAnswer( tree ,  lazy ,  mid+1, high, startR, endR ,  treeNode*2+1);
    }else if(endR <= mid){
        //that's means our end is so far to mid or equal so need to travers in left subtree
        return getAnswer( tree ,  lazy ,  low, mid, startR, endR ,  treeNode*2);
    }
    ll left=getAnswer( tree ,  lazy ,  low, mid, startR, endR ,  treeNode*2);   //traverse right
    ll right=getAnswer( tree ,  lazy ,  mid+1, high, startR, endR ,  treeNode*2+1); //and left
    return (left+right);//for any node total sum=(leftTreeSum+rightTreeSum)
}
int main()
{
    int nTestCase;
    cin>>nTestCase;
    while(nTestCase--)
    {
        ll n,nQuery;
        cin>>n>>nQuery;
        ll *tree=new ll[3*n]();
        ll *lazy=new ll[3*n]();
        while(nQuery--)
        {
            int choice;
            cin>>choice;
            if (choice==0)
            {
                ll startR,endR,updateValue;
                cin>>startR>>endR>>updateValue;
                //0:- start index , n-1 end index ,1 treeIndex tree is our segment tree and lazy is our lazy segment tree
                updateSegementLazyTree(tree , lazy , 0, n-1, startR-1 , endR-1 , updateValue , 1);
            // for (int i = 0; i < 3*n; ++i)
            //  {
            //      cout<<i<<"\t"<<tree[i]<<"\t"<<lazy[i]<<endl;
            //  }
            }else{
                ll startR,endR;
                cin>>startR>>endR;
                ll answer=getAnswer(tree , lazy , 0, n-1 , startR-1 , endR-1 , 1);
                cout<<answer<<endl;
            }
        }
    }
}

updateSegementLazyTree() take two arrays of size 4*n because the total number of possible nodes with the length of log(n) will be 2*2^log(n) that at most is 4*n. Then we also need interval[startR,endr] and updateValue that we maintain through recrusion. Tree[treeNode] represents the sum of all elements from left and right.

Sample input looks like:

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

So for the first query we have to update 2-4 with +26. Instead of updating all elements between 2-4 we just store it in our lazy tree and whenever we access any node from the tree we first check weather this node has any pending update. If there are no pending updates, then complete and shift this to their child.

q1:- 0 2 4 26
tree[0,78,78,0,26,52,0,0,0,26] 

try to make tree index; for left tree(2*i+1) and right(2*i+1) 1-st index is at least 78 i.e. top of tree so from [0,n-1] current max is 78.

tree[treeNode] += (high-low+1)*lazy[treeNode];

If we add x from low index to high then in overall sub array i have added (high-low+1)*x ; -1 because of indexing from 0.

Then, before accessing any node from tree we lazy check weather that node has any pending update. if (lazy[treeNode]!=0) If it has, then update and transfer lazy to their child. Keep doing that for left subtree and right subtree as well.

Then we reach getAnswer() within range[startR,endR] As I mentioned before, we first check for pending updates for each affected node. If true then it completes that update and call recursively left and right subtree according to the interval.

At the end we have the sum of leftSubtree and sum of rightsubtree of root node, add them and return them.

Time Complexity

In update, getAnswer(), in worst case will have to traverse the entire tree i.e. height of tree O(2*Log N). 2*log n because it is the worst case we have to travel in left and right subtree e.g. for interval [0-n-1].

For k query, overall time complexity would be O(K*log n).