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 : -
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’
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 : - 0zzisK - Online C++0x Compiler & Debugging Tool - Ideone.com
Happy Coding!
UPDATE:-NngMkb - Online C++0x Compiler & Debugging Tool - Ideone.com
(ABOVE CODE HANDLES UPDATE QUERIES AS WELL )