Editing Interval tree (section)

{{Distinguish|segment tree}}
{{Short description|Tree data structure to hold intervals}}
In [[computer science]], an '''interval tree''' is a [[Tree (data structure)|tree data structure]] to hold [[Interval (mathematics)|intervals]]. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is often used for windowing queries,<ref>https://personal.us.es/almar/cg/08windowing.pdf {{Bare URL PDF|date=March 2022}}</ref> for instance, to find all roads on a computerized map inside a rectangular viewport, or to find all visible elements inside a three-dimensional scene. A similar data structure is the [[segment tree]].

The trivial solution is to visit each interval and test whether it intersects the given point or interval, which requires <math>O(n)</math> time, where <math>n</math> is the number of intervals in the collection. Since a query may return all intervals, for example if the query is a large interval intersecting all intervals in the collection, this is [[asymptotically optimal]]; however, we can do better by considering [[output-sensitive algorithm]]s, where the runtime is expressed in terms of <math>m</math>, the number of intervals produced by the query. Interval trees have a query time of <math>O(\log n + m)</math> and an initial creation time of <math>O(n \log n)</math>, while limiting memory consumption to <math>O(n)</math>. After creation, interval trees may be dynamic, allowing efficient insertion and deletion of an interval in <math>O(\log n)</math> time. If the endpoints of intervals are within a small integer range (''e.g.'', in the range <math>[1, \ldots, O(n)]</math>), faster and in fact optimal data structures exist<ref name=Schmidt2009>[[Jens M. Schmidt]]. ''Interval Stabbing Problems in Small Integer Ranges''. [https://dx.doi.org/10.1007/978-3-642-10631-6_18 DOI]. ISAAC'09, 2009</ref><ref>[[Range Queries#Semigroup operators]]</ref> with preprocessing time <math>O(n)</math> and query time <math>O(1+ m)</math> for reporting <math>m</math> intervals containing a given query point (see<ref name=Schmidt2009/> for a very simple one).