What is the best(time) method to solve Range minimum query questions **without** using fenwick tree ,

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 :

@vermashubhang : The construction time for “segment tree” is O(N log(N) ) .

@randomizer :

Segment trees and Fenwick trees and very similar , you can say a Fenwick tree is a simplification of segment tree .

A different approach is “Square Root Decomposition” . It give O(N) construction time ( better than segment tree ) . However query time is O(sqrt(N)) or O(N^0.5) .

If the number of queries is O(N^0.5) , then “Square Root Decomposition” can do both construction and answering of queries in O(N) . The segment tree / fenwick tree would take O(N log(N) ) time .

However if number of queries is O(N) , then “Square Root Decomposition” will take O(N^1.5) time .

The segment tree / fenwick tree will still take O(N log(N) ) time .

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).

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^j-1], minimum value in the interval [R-2^j+1,R]}**, where **j** is the largest value such that **2^j <= the length of the interval** (i.e. R-L+1).

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.