Segment tree
In computer science, a segment tree, also known as a statistic tree, is a tree data structure used for storing information about intervals, or segments. It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, it's a structure that cannot be modified once it's built. A similar data structure is the interval tree. A segment tree for a set of "n" intervals uses "O"("n" log "n") storage and can be built in "O"("n" log "n") time. Segment trees support searching for all the intervals  that contain a query point in time "O"(log "n" + "k"), "k" being the number of retrieved intervals or segments. Applications of the segment tree are in the areas of computational geometry, geographic information systems and machine learning. The segment tree can be generalized to higher dimension spaces. Structure description. "This section describes the structure of a segment tree in a one-dimensional space." Let "S" be a set of intervals, or segments. Let "p", "p", ..., "p" be the list of distinct interval endpoints, sorted from left to right. Consider the partitioning of the real line induced by those points . The regions of this partitioning are called "elementary intervals". Thus, the elementary intervals are, from left to right: That is, the list of elementary intervals consists of open intervals between two consecutive endpoints "p" and "p", alternated with closed intervals consisting of a single endpoint. Single points are treated themselves as intervals because the answer to a query is not necessarily the same at the interior of an elementary interval and its endpoints. Given a set of intervals, or segments, a segment tree "T" for is structured as follows: Storage requirements. "This section analyzes the storage cost of a segment  tree in a one-dimensional space." A segment tree "T" on a set of "n" intervals uses "O"("n" log "n") storage. Construction. "This section describes the construction of a segment tree in a one-dimensional space." A segment tree from the set of segments , can be built as follows. First, the endpoints of the intervals in are sorted. The elementary intervals are obtained from that. Then, a balanced binary tree is built on the elementary intervals, and for each node "v" it is determined the interval Int("v") it represents. It remains to compute the canonical subsets for the nodes. To  achieve this, the intervals in are inserted one by one into the segment tree. An interval "X" = ["x", "x′"] can be inserted in a subtree rooted at "T", using the following procedure: The complete construction operation takes "O"("n" log "n") time, "n" being the number of segments in . Query. "This section describes the query operation of a segment tree in a one-dimensional space." A query for a segment tree, receives a point "q"(should be one of the leaves of tree), and retrieves a list of all the segments stored which contain the point "q". Formally stated; given a  node (subtree) "v" and a query point "q", the query can be done using the following algorithm: In a segment tree that contains "n" intervals, those containing a given query point can be reported in "O"(log "n" + "k") time, where "k" is the number of reported intervals. Generalization for higher dimensions. The segment tree can be generalized to higher dimension spaces, in the form of multi-level segment trees. In higher dimensional versions, the segment tree stores a collection of axis-parallel (hyper-)rectangles, and can retrieve the rectangles that contain a given query point. The structure uses "O"("n" log  n) storage, and answers queries in "O"(log "n"). 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. Notes. A query that asks for all the intervals containing a given point is often referred as a "stabbing query". The segment tree is less efficient than the interval tree for range queries in one dimension, due to its higher storage requirement: "O"("n" log "n") against the O("n") of the interval tree. The importance of the segment  tree is that the segments within each node’s canonical subset can be stored in any arbitrary manner. For "n" intervals whose endpoints are in a small integer range (e.g., in the range [1,…,"O"("n")]), optimal data structures exist with a linear preprocessing time and query time "O"(1 + "k") for reporting all "k" intervals containing a given query point. Another advantage of the segment tree is that it can easily be adapted to counting queries; that is, to report the number of segments containing a given point, instead of reporting the segments themselves. Instead of storing the intervals in  the canonical subsets, it can simply store the number of them. Such a segment tree uses linear storage, and requires an "O"(log "n") query time, so it is optimal. 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. But the structures can be used as associated structure of segment trees. History. The segment tree was invented by Jon Bentley in 1977; in "Solutions to Klee’s rectangle problems".