topcoder segment tree tutorial why the code for query is modifying the content of M array in last 4 lines of code return M[node]=p2 .Instead of this he could have just returned the node index. Modified M array won't be able to handle future RMQ [range minimum Queries].
} asked 02 Nov '14, 14:24

For any range, we will use M[node], as it is, only if it is completely in range, (as repeating the procedure for that same range will give same value). However, in case of some range, which is just a part of M[node]'s range, we are not actually looking for that whole range covered by M[node], we will recompute position of minimum element for our range and use the new value. If a node is not in required range, 1 is returned, and it is ignored. Only those values, which are in required range are compared and minimum is computed of of them and position of this minimum is again put in the M[node] and we use this new M[node]. We don't care if previous M[node] consisted of a different range. We have recomputed new one for our own range. And this recomputation will always happen whenever there is a difference in required range and range of a particular M[node]. answered 02 Nov '14, 19:45

but whey we need to recompute ??? for eg ... if 1st RMQ intersects the leaves on left and right side of the root.... then we are modifying the M[root]. Thus M[root] will contain the minimum of 1st RMQ query. Now when we fire 2nd RMQ which perfectly intersects the root node i.e RMQ[0..n1].. then we will get wrong result...or we need to recompute the minimum ?? answered 06 Nov '14, 17:30
