Search code examples
cdata-structuressegment-tree

Update Segment tree if the given value is less than the current value

I have been wondering if it is possible for a segment tree to be updated only if the updated new value is less than the current value.

eg. a[i] to a[j] is to updated to x

if(a[k]>x)
  a[k]=x;

i<=k<=j

How can this be done?

Lazy propagation is what I'm trying for.

Solution

  • What i understand from your question is that you are trying to update a continuous segment of array if the new value is less than that, If yes then the answer is Segment Tree. Steps should be:

    1- Construct a array of size of segment tree (2*n -1 = n for elements of array and as segment tree is complete binary tree, there will be n-1 internal nodes) and initialize it with the value greater than maximum possible value.

    2- Now update the value at a segment in segment tree if the range of updation matches exactly with the segment range of segement tree. Ex you want to update from 2-4 segment with value 4 then just traverse to find the exact segement in segment tree that can be 2-4 as a single segment or may be divided in two say 2 and 3-4, just update that segment.

    3- repeat step 2 for all your updation(update if value is less than the current value in segment tree).

    4- After all updation done, make a parser that will traverse whole segment tree top to bottom and bring down the minimum weight to the n leaf nodes.