CODEWITHSUNDEEP
cdata-structuressegment-tree
user5082201
user5082201

Reputation:

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.

Upvotes: 1

Views: 191

Answers (1)

suraj3
suraj3

Reputation: 26

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.

Upvotes: 1

Related Questions