is , where k is the number of points in the query interval. This can be reduced to using a variant of fractional cascading. See also k-d tree Segment tree Range searching References External links Range and Segment Trees in CGAL, the Computational Geometry Algorithms Library. Lecture 8: Range Trees, Marc van Kreveld. Range Trees using PAM, the parallel augmented map library. Trees (data structures) Geometric data structures