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

        riddles >> cs >> Maximum in every interval
        
(Message started by: Barukh on Jun 2nd, 2012, 10:11pm)
Title: Maximum in every interval
Post by Barukh on Jun 2nd, 2012, 10:11pm
Consider a set of records each holding a pair of numerical values (x, y).

Design an efficient dynamic (i.e. with insertions) data structure for the following query: Given a pair x1, x2, return a record with maximal y-value for which x-value lies in the interval [x1, x2].

What is the complexity of insertion and query operations?
Title: Re: Maximum in every interval
Post by towr on Jun 3rd, 2012, 1:15am
You could use a tree, which would be O(log(n)) for queries and insertion.. Store the maximum y for each subtree.
Title: Re: Maximum in every interval
Post by Barukh on Jun 3rd, 2012, 2:02am
Terse, but illuminating  ;)
Title: Re: Maximum in every interval
Post by Ela on Jul 17th, 2012, 2:08am
::)nice!!
Title: Re: Maximum in every interval
Post by sachu on Jul 25th, 2012, 12:22am
I couldn,t understand how the binary tree helps.. Could u please elaborate.....
Title: Re: Maximum in every interval
Post by towr on Jul 25th, 2012, 10:25am
Because each subtree represents a range, you only need to look at a few nodes to find the maximum.
For example in the attachment, the leaf node have x values 1 through 16; each internal node represent a range and contains the maximum in that range. To find the maximum in the range 5-12, you will only need to look at the nodes coloured red to find the maximum. The leaf nodes of the coloured subtree represent the subranges 4, 5-8 and 9-12.
Title: Re: Maximum in every interval
Post by sachu on Jul 25th, 2012, 9:56pm
gud1....
Title: Re: Maximum in every interval
Post by R on Sep 14th, 2012, 8:54pm

on 07/25/12 at 10:25:40, towr wrote:
Because each subtree represents a range, you only need to look at a few nodes to find the maximum.
For example in the attachment, the leaf node have x values 1 through 16; each internal node represent a range and contains the maximum in that range. To find the maximum in the range 5-12, you will only need to look at the nodes coloured red to find the maximum. The leaf nodes of the coloured subtree represent the subranges 4, 5-8 and 9-12.

Are you using standard BST or some custom trees to store 'intervals'. I've read somewhere about interval-trees which specifically store (x,y) type of pairs.
Title: Re: Maximum in every interval
Post by towr on Sep 14th, 2012, 11:42pm
A specialized tree would probably be simplest. Otherwise you need to use a custom compare-function or something. But I haven't really considered it at that level of detail.
Title: Re: Maximum in every interval
Post by R on Sep 15th, 2012, 12:55am

on 09/14/12 at 23:42:41, towr wrote:
A specialized tree would probably be simplest. Otherwise you need to use a custom compare-function or something. But I haven't really considered it at that level of detail.

Actually I am not able to understand how the tree is being created in your solution. Could you please elaborate more? Thanks.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board