set representation question

[John Meacham]

On Wed, Nov 12, 2003 at 03:00:38PM +1300, Tom Pledger wrote:
> The total time (including the up front time for building the data
> structure) can't go below O(n+m), because if it did, you'd be
> neglecting to look at some of the elements at all.

that would be true if there wern't a total ordering on integers, since
there is you can cut out whole ranges of them without looking at the
actual values.

my intuition says something like binary trees annotated with the minimum
and maximum value contained beneath each node so you may prune whole
subtrees in constant time...

        John

-- 
---------------------------------------------------------------------------
John Meacham - California Institute of Technology, Alum. - john at foo.net
---------------------------------------------------------------------------