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 :
2 Likes
@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 .
5 Likes
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).
5 Likes
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.