Segment tree

[1] Applications of the segment tree are in the areas of computational geometry, geographic information systems and machine learning.

Let p1, p2, ..., pm be the list of distinct interval endpoints, sorted from left to right.

An interval X = [x, x′] can be inserted in a subtree rooted at T, using the following procedure:[4] The complete construction operation takes O(n log n) time, n being the number of segments in I.

Visiting every node takes constant time (assuming that canonical subsets are stored in a simple data structure like a linked list).

The sum of all the kv for all nodes v visited, is k, the number of reported segments.

Lemma —  Any interval [x, x′] of I is stored in the canonical set for at most two nodes at the same depth.

The use of fractional cascading lowers the query time bound by a logarithmic factor.

The use of the interval tree on the deepest level of associated structures lowers the storage bound by a logarithmic factor.

Such a segment tree uses linear storage, and requires an O(log n) query time, so it is optimal.

[8] Higher dimensional versions of the interval tree and the priority search tree do not exist; that is, there is no clear extension of these structures that solves the analogous problem in higher dimensions.

[6] The segment tree was invented by Jon Bentley in 1977; in "Solutions to Klee’s rectangle problems".