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@foo.net ---------------------------------------------------------------------------