Author |
Topic: Re: Minimal Range Query Problem (Read 586 times) |
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
 |
Re: Minimal Range Query Problem
« on: May 15th, 2006, 2:09am » |
 Quote  Modify
|
Obviously if query time can be O(n), space requirement can be brought back to O(n), just search for the minimimum between i and j.
You can make some improvement by for each a[k] giving the next lower a[l] with l > k. It costs a bit more preprocessing though
Given enough preprocessing you might also be able to find to find a perfect hash, giving constant query time and linear space requirement.
|
|
 IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
KWillets
Junior Member
Posts: 84
|
|
Re: Minimal Range Query Problem
« Reply #1 on: May 18th, 2006, 12:26pm » |
Quote Modify
|
This (Range Min query, or RMQ) can be reduced to the LCA problem, which is itself reducible to a special case of RMQ where the values only change by +/-1 between successive elements. The trick is to map a[] to a tree where the LCA of two elements is the minimum between them.
So that's:
RMQ
LCA
RMQ+/-1 = O(n)
It took a dozen or so tries to dredge this up via web searches; it's another MIT lecture note:
http://theory.lcs.mit.edu/classes/6.897/spring05/lec/lec15.pdf
|
|
IP Logged |
|
|
|
KWillets
Junior Member
Posts: 84
|
|
Re: Minimal Range Query Problem
« Reply #2 on: May 18th, 2006, 1:18pm » |
Quote Modify
|
An interesting subproblem of the above is how to create a Cartesian tree from a[] in O(n) time. A Cartesian tree is one where the root node corresponds to the (or a) minimal element of a[], and the left and right subtrees contain the elements left and right, respectively, of the min, with the same property satisfied on those subarrays, recursively down the tree.
That is, the root has the minimum of a[1..n], at, say, index j. The left subtree contains the elements a[1...j-1], and root of the subtree has the minimum of these elements, continuing down the tree.
eg:
3 1 4 2
maps to:
(difficult to format, imagine a tree)
1
3 2
4
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print