Editing Interval tree (section)

==== With an interval ====

For a result interval <math>r</math> to intersect our query interval <math>q</math> one of the following must hold:

* either the start or end point of <math>r</math> is in <math>q</math>; or
*<math>r</math> completely encloses <math>q</math>.

{{Confusing|date=February 2020}}
We first find all intervals with start and/or end points inside <math>q</math> using a separately-constructed tree. In the one-dimensional case, we can use a search tree containing all the start and end points in the interval set, each with a pointer to its corresponding interval. A binary search in <math>O(\log n)</math> time for the start and end of <math>q</math> reveals the minimum and maximum points to consider. Each point within this range references an interval that overlaps <math>q</math> and is added to the result list. Care must be taken to avoid duplicates, since an interval might both begin and end within <math>q</math>. This can be done using a binary flag on each interval to mark whether or not it has been added to the result set.

Finally, we must find intervals that enclose <math>q</math>. To find these, we pick any point inside <math>q</math> and use the algorithm above to find all intervals intersecting that point (again, being careful to remove duplicates).