What is the best(time) method to solve Range minimum query questions without using fenwick tree , asked 19 Mar '14, 20:59

@vermashubhang : The construction time for "segment tree" is O(N log(N) ) . answered 19 Mar '14, 21:28
Sorry for the error. I corrected it to O(N*log(N)). But for range minimum/maximum trees as asked by @randomizer it is O(N).
(19 Mar '14, 21:39)

The best that is possible on a static sequence (i.e. no updates) is O(N) preprocessing time + O(1) query time, which is actually optimal (as the size of the input is O(N) and you cannot do better than O(1) per query). But getting the O(N) preprocessing part is not so easy. What is easy is to do O(N*log(N)) preprocessing (for each position compute the minimum value over an interval of length 2^j starting and ending at that position, for each j from 0 to log(N)). Then, with this information, you can answer a query in O(1) time by getting the minimum of two precomputed values. If the query is for the interval [L,R] then the answer is min{minimum value in the interval [L, L+2^j1], minimum value in the interval [R2^j+1,R]}, where j is the largest value such that 2^j <= the length of the interval (i.e. RL+1). answered 19 Mar '14, 22:49

Range Minimum queries can also be solved by using Segment Tree Data structure. The basic construction cost of a segment tree is O(N*log(N)) , along with linear space and the time for query is O(log(N)). Its space usage is more as compared to Binary Indexed Trees. A very nice tutorial on segment trees can be found at the following links :
answered 19 Mar '14, 21:14

Range minimum Query can also be solved using sparse table and lowest common ancestor(LCA) A sparse table requires O(n * log n) time for construction and O(1) to answer each query whereas LCA takes O(n) time for constrution and O(1) time per query. answered 12 Jan, 00:38
