wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Re: Minimal Range Query Problem
        
(Message started by: towr on May 15^th, 2006, 2:09am)

Title: Re: Minimal Range Query Problem
Post by towr on May 15^th, 2006, 2:09am

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.

Title: Re: Minimal Range Query Problem
Post by KWillets on May 18^th, 2006, 12:26pm

[hide]
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
[/hide]

Title: Re: Minimal Range Query Problem
Post by KWillets on May 18^th, 2006, 1:18pm

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