You are not logged in. Please login at www.codechef.com 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

4★randomizer
1462311
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 .

link

answered 19 Mar '14, 21:28

vineetpaliwal's gravatar image

6★vineetpaliwal
12.4k47107170
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) vermashubhang5★

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

link

answered 19 Mar '14, 22:49

mugurelionut's gravatar image

7★mugurelionut
9.8k266989
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 :

http://sportcoder.com/segment-trees/
http://letuskode.blogspot.in/2013/01/segtrees.html

link

answered 19 Mar '14, 21:14

vermashubhang's gravatar image

5★vermashubhang
1.5k11025
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.

link

answered 12 Jan, 00:38

jaideeppyne's gravatar image

4★jaideeppyne
712
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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

Question tags:

×156
×50
×30

question asked: 19 Mar '14, 20:59

question was seen: 5,638 times

last updated: 12 Jan, 00:38