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 : -

- L R…means find the minimum number in the range [L,R] of the array.
- 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 : -

https://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/

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’

Can our segment tree return ‘3’ on querying???

Yes, It CAN!!!

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

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

We do the querying in the same way

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

My implementation : - https://ideone.com/0zzisK

*Happy Coding!*

UPDATE:-https://ideone.com/NngMkb

(ABOVE CODE HANDLES UPDATE QUERIES AS WELL )