Some questions in regards with 'Array Queries' problem

#1

In the solution there are the following lines:

    if(r>=n)
    {
        update(0,0,n-1,l,n-1,a[i]);
        update(0,0,n-1,0,r-n,a[i]);
    }
    else
    {
        update(0,0,n-1,l,r,a[i]);
    }

And then in the queries loop again there is something similar:

    if(r>=n) // cyclic update on ranges [l,n-1] and [0,r-n].
    {
         update(0,0,n-1,l,n-1,y-a[l]);
         update(0,0,n-1,0,r-n,y-a[l]);
    }
    else //simple update on range [l,r]
    {
          update(0,0,n-1,l,r,y-a[l]);
    }

Could you please be more detailed about the following points:

  1. Why there are two calls of update(…)
  2. Why in the first call the [l, r] is [l, n-1] and in the second call [l, r] = [0, r - n]
  3. Why in the query section the update was called with y - a[l] as a val ?
#2

hello @begginner_cp

becuase r has crossded the last index so that means this will have some part of prefix(starting) array as well thats why we are breaking in two section
section one dealing with suffix array [l…n-1] and section two is dealing with prefix array [0…r-n]

final value is y and current value is a[l]
so what is net update ? it is y-a[l] that means we need to increment all values by this much. thats is the reason for y-a[l]

1 Like
#3

Ok, I got it thanks. One more thing I want to understand.
Why we are not building the segment tree, and instead of that we are updating it.

Here is the code with help of which the tree is updating at the begging:
for(int i=0;i<n;i++)
{
cin>>a[i];
int l=i,r=i+k-1;
if(r>=n)
{
update(0,0,n-1,l,n-1,a[i]);
update(0,0,n-1,0,r-n,a[i]);
}
else
{
update(0,0,n-1,l,r,a[i]);
}
}
Let’s say k = 3 and i = 0, then l = 0 and r = 2 and we are updating the segment [0-2] with some value of a[i].
Then i becomes 1 and in regards with that l = 1 and r = 3, so this time we are updating the segment [1- 3] but the segments [0 - 2] and [1 - 3] have intersection and element from from segment [0-2] will get updates with value which is intended for segment [1 - 3]. Could you pleas explain this please ?
Thanks in advance.

#4

@begginner_cp

we are building segement tree only , here every number have impact on a range so doing a point update will not work that is the reason why we are not using our build build function to build the segment tree

we are building sum segment tree , so obviously it will overlap for nodes

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.