 | This article has multiple issues. Please helpimprove it or discuss these issues on thetalk page.(Learn how and when to remove these messages) (Learn how and when to remove this message)
|
Incomputer science, thesegment tree is adata structure used for storing information aboutintervals or segments. It allows querying which of the stored segments contain a given point. A similar data structure is theinterval tree.
A segment tree for a setI ofn intervals usesO(n logn) storage and can be built inO(n logn) time. Segment trees support searching for all the intervals that contain a query point in timeO(logn +k),k being the number of retrieved intervals or segments.[1]
Applications of the segment tree are in the areas ofcomputational geometry,geographic information systems andmachine learning.
The segment tree can be generalized to higherdimension spaces.
LetI be a set of intervals, or segments. Letp1,p2, ...,pm 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 calledelementary intervals. Thus, the elementary intervals are, from left to right:
That is, the list of elementary intervals consists of open intervals between two consecutive endpointspi andpi+1, 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.[2]
Given a setI of intervals, or segments, a segment treeT forI is structured as follows:
A segment tree from the set of segmentsI, can be built as follows. First, the endpoints of the intervals inI are sorted. The elementary intervals are obtained from that. Then, a balanced binary tree is built on the elementary intervals, and for each nodev it is determined the interval Int(v) it represents. It remains to compute the canonical subsets for the nodes. To achieve this, the intervals inI are inserted one by one into the segment tree. An intervalX = [x,x′] can be inserted in a subtree rooted atT, using the following procedure:[4]
The complete construction operation takesO(n logn) time,n being the number of segments inI.
Visiting every node takes constant time (assuming that canonical subsets are stored in a simple data structure like alinked list). When we visit nodev, we either storeX atv, or Int(v) contains an endpoint ofX. As proved above, an interval is stored at most twice at each level of the tree. There is also at most one node at every level whose corresponding interval containsx, and one node whose interval containsx′. So, at most four nodes per level are visited. Since there areO(logn) levels, the total cost of the insertion isO(logn).[1]
A query for a segment tree receives a pointqx(should be one of the leaves of tree), and retrieves a list of all the segments stored which contain the pointqx.
Formally stated; given a node (subtree)v and a query pointqx, the query can be done using the following algorithm:
In a segment tree that containsn intervals, those containing a given query point can be reported inO(logn +k) time, wherek is the number of reported intervals.
The query algorithm visits one node per level of the tree, soO(logn) nodes in total. On the other hand, at a nodev, the segments inI are reported inO(1 +kv) time, wherekv is the number of intervals at nodev, reported. The sum of all thekv for all nodesv visited, isk, the number of reported segments.[5]
A segment treeT on a setI ofn intervals usesO(n logn) storage.
Lemma— Any interval [x,x′] ofI is stored in the canonical set for at most two nodes at the same depth.
Letv1,v2,v3 be the three nodes at the same depth, numbered from left to right; and let p(v) be the parent node of any given nodev. Suppose [x,x′] is stored atv1 andv3. This means that [x,x′] spans the whole interval from the left endpoint of Int(v1) to the right endpoint of Int(v3). Note that all segments at a particular level are non-overlapping and ordered from left to right: this is true by construction for the level containing the leaves, and the property is not lost when moving from any level to the one above it by combining pairs of adjacent segments. Now either parent(v2) = parent(v1), or the former is to the right of the latter (edges in the tree do not cross). In the first case, Int(parent(v2))'s leftmost point is the same as Int(v1)'s leftmost point; in the second case, Int(parent(v2))'s leftmost point is to the right of Int(parent(v1))'s rightmost point, and therefore also to the right of Int(v1)'s rightmost point. In both cases, Int(parent(v2)) begins at or to the right of Int(v1)'s leftmost point. Similar reasoning shows that Int(parent(v2)) ends at or to the left of Int(v3)'s rightmost point. Int(parent(v2)) must therefore be contained in [x,x′]; hence, [x,x′] will not be stored atv2.
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 usesO(n logdn) storage, and answers queries inO(logdn) time.
The use offractional cascading lowers the query time bound by a logarithmic factor. The use of theinterval tree on the deepest level of associated structures lowers the storage bound by a logarithmic factor.[6]
A query that asks for all the intervals containing a given point is often referred as astabbing query.[7]
The segment tree is less efficient than theinterval tree for range queries in one dimension, due to its higher storage requirement:O(n logn) 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.[7]
Forn intervals whose endpoints are in a small integer range (e.g., in the range [1,...,O(n)]), optimal data structures[which?] exist with a linear preprocessing time and query timeO(1 +k) for reporting allk 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 anO(logn) query time, so it is optimal.[8]
Higher dimensional versions of the interval tree and thepriority 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.[6]
![[icon]](/mt/?noimg=&dark=on&url=https%3a%2f%2fen.wikipedia.org%2fwiki%2fFile%3aWiki_letter_w_cropped.svg) | This sectionneeds expansion. You can help byadding missing information.(November 2007) |
The segment tree was invented byJon Bentley in 1977; in "Solutions to Klee’s rectangle problems".[7]
