I tried to write the code but stucked in update part......i have stored f(xk) in segment tree node..so check it once please and tell me about update part ....becoz A[x]=y put krna hai ,

#1
#2

Hey @Muskan-Gupta-598128740703036,

In this question we will be using something called as Lazy Propagation.

Using a general approach to update an element in a Segment tree, we need to look at the interval in which the element is and recurse accordingly on the left or the right child.
Complexity of update an element will be O(logN) in segment tree.

Now if we use this approach to update elements in an interval, it will give TLE.
When we have to update an interval from l to r, instead of a single element. One solution is to update all the elements one by one. Complexity of this approach will be O(N) per operation since where are N elements in the array and updating a single element will take O(LogN) time.

Updating an interval (Lazy Propagation):

To avoid multiple call to update function, we can modify the update function to work on an interval.

Let’s be Lazy i.e., do work only when needed. How?
When we need to update an interval, we will update a node and mark its child that it needs to be updated and update it when needed.
For this we need an array lazy[ ] of the same size as that of segment tree. Initially all the elements of the lazy[ ] array will be 0 representing that there is no pending update.

If there is non-zero element lazy[k] then this element needs to update node k in the segment tree before making any query operation.

To update an interval we will keep 3 things in mind.

  1. If current segment tree node has any pending update, then first add that pending update to current node.

  2. If the interval represented by current node lies completely in the interval to update, then update the current node and update the lazy[] array for children nodes.

  3. If the interval represented by current node overlaps with the interval to update, then update the nodes as the earlier update function

Since we have changed the update function to postpone the update operation, we will have to change the query function also. The only change we need to make is to check if there is any pending update operation on that node. If there is a pending update operation, first update the node and then work same as the query function.

Here is the corrected code: https://ide.codingblocks.com/s/206892

#3

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.