More about Segment Trees(which returns the minimum index as well) :-)

tutorial
1

Prerequisites:- Basic knowledge of segment trees.

So, we know the range minimum problem very well. We are given an array of integers and lots of queries .

Queries are of the form : -

  1. L R…means find the minimum number in the range [L,R] of the array.
  2. L X…means update the index ‘L’ with ‘X’ , that is, a[L]=X .

Both the above operations can be done in O(logN) time using segment trees.

Here, is the implementation : -
Segment Tree | Range Minimum Query - GeeksforGeeks

But, now the question arises, how to return the index of the minimum value in range [L.R]…???
Say, the array is [1,2,1,1,1,1,1,1,1] ;
and we have to find the index of the minimum number in range [2,9]…so…the minimum number is ‘1’ and indices are :- {3,4,5,6,7,8,9}…lets focus on the minimum index which is ‘3’ :slight_smile:
Can our segment tree return ‘3’ on querying???
Yes, It CAN!!! :slight_smile: :slight_smile:

Here is how to do it : -

While building the segment tree, in this part : -

if(start==end)
{

segtree[node]=index;

}

Directly store the index of elements in the leaf nodes of segment tree :slight_smile:

Now, say, segtree[6]=4 and segtree[7]=8…

Now segtree[3] is always dependent on the values of segtree[ (2)(3)==6] and segtree[(2)(3) +1==7] , so which index should be stored in segtree[3]??

We check if a[4] is bigger or a[6] is bigger, whichever is the smaller value, we store it in segtree[3] … i,e… segtree[3]==segtree[6] OR segtree[3]==segtree[7]

In this way we build the complete segment tree :slight_smile:

We do the querying in the same way :slight_smile:

Bonus point : - what if segtree[7]==segtree[6], then what will be the value of the segtree[3]??

It will always be segtree[ (2)(3)==6]…which is the left node…

Why the left node??

Because the left node will always give the minimum index :slight_smile:

My implementation : - 0zzisK - Online C++0x Compiler & Debugging Tool - Ideone.com

Happy Coding!:slight_smile:

UPDATE:-NngMkb - Online C++0x Compiler & Debugging Tool - Ideone.com
(ABOVE CODE HANDLES UPDATE QUERIES AS WELL :slight_smile: )

6 Likes
2

Hmm! Great, segment tree is really powerful. When I saw the post title, I immediately thought of storing the whole segments on Nodes(Merge Sort tree). Turns out that isn’t needed.

1 Like
3

Yup, that is not needed here and anyways it is not very efficient(its inefficient in this case :stuck_out_tongue: )
As it will take O(log(n)^2) time :slight_smile: :slight_smile:
Thanks.

4

Can we make seg tree support lazy updates?

5

Yes you can do that, but when I need lazy for such operation I prefer storing pairs {index,value}
Reason is though you will update the segment but you are not reaching to the lowest depth of the tree to make change in the array in order to retrieve an updated value from the array.

    if(lazy[node] != 0){
        tree[node] = make_pair(start,lazy[node]);
        if(start != end)lazy[node << 1] = lazy[node << 1 | 1] = lazy[node];
        lazy[node] = 0;
    }
6

Can we get the maximum index as well using similar approach?