Array Queries-1

#1

Can anyone help in this can’t figure a way out

#2

What’s the issue you are facing?
Are you unable to think of an approach?

#3

Yes what should be the structure of the seg.tree what should the nodes store ,please provide some hint.

#4

Lets first calculate f() function for each index and call it array ar.
Then we can simply do cummalative sum kind of thing that we generally do using segment tree.

#5

I think this kind of a thing to build our array.
Then you can use segment tree for further purpose.
cin>>n>>k>>q;
for(int i=0;i<n-1;i++)
cin>>v[i+1];
cin>>v[0];

    int sum=0;
    for(int i=0;i<k;i++)
        sum+=v[i];

    ar[0]=sum;


    int cur=k;
    for(int j=0;j<n-1;j++)
    {
        sum+=v[(cur+j)%n] - v[(cur+j-k)%n];
        ar[j+1]=sum;
    }
#6

And what to do if a update query comes. Calculate f(i,k) for that index again and update our tree??

#7

You wont have to calculate f(i,k) again.
You can get the difference of prev value and updated value, and reflect the required difference in those indexes required.

Have a look at this code just for reference.

You can calculate indices where the change has to be reflected. Update their value in array and segment tree. I think that would work fine.

#8

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.