You are not logged in. Please login at to post your questions!


Range minimum query , without using fenwick tree

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

asked 19 Mar '14, 20:59

randomizer's gravatar image

accept rate: 11%

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


answered 19 Mar '14, 21:28

vineetpaliwal's gravatar image

accept rate: 12%

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

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


answered 19 Mar '14, 22:49

mugurelionut's gravatar image

accept rate: 16%

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

vermashubhang's gravatar image

accept rate: 23%

edited 19 Mar '14, 21:34

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

jaideeppyne's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol



Asked: 19 Mar '14, 20:59

Seen: 5,296 times

Last updated: 12 Jan, 00:38