Method 4 for implementing van Emde Boas with linear space, described in my last post, is due to [Alstrup, Brodal, Rauhe: STOC'01]. They worked on static range reporting in 1 dimension: preprocess a set of integers S, and answer query(a,b) = report all points in S ∩ [a,b]. This is easier than predecessor search: you can first find the predecessor of a and then output points in order until you exceed b. Using van Emde Boas, we would achieve a linear-space data structure with query time O(lglg u + k), where k is the number of points to be reported.
Static 1D range reporting can be solved with O(n) space and O(1+k) query time.
- if LCA(a,b) is a branching node, look at the two descendant branching nodes. If the interval [a,b] is nonempty, it must contain either the max in the tree of the left child, or the min in the tree of the right child.
- if LCA(a,b) is an active node, go to its lowest branching ancestor, and do something like the the above.
- if LCA(a,b) is not an active node, the interval [a,b] is certainly empty!
- active nodes at depth i·√lg u ;
- active nodes less than √lg u levels below a branching node.