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 p1, 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 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 pi and pi+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.
Given a set I of intervals, or segments, a segment tree T for I is structured as follows:
- T is a binary tree.
- Its leaves correspond to the elementary intervals induced by the endpoints in I, in an ordered way: the leftmost leaf corresponds to the leftmost interval, and so on. The elementary interval corresponding to a leaf v is denoted Int(v).
- The internal nodes of T correspond to intervals that are the union of elementary intervals: the interval Int(N) corresponding to node N is the union of the intervals corresponding to the leaves of the tree rooted at N. That implies that Int(N) is the union of the intervals of its two children.
- Each node or leaf v in T stores the interval Int(v) and a set of intervals, in some data structure. This canonical subset of node v contains the intervals from I such that contains Int(v) and does not contain Int(parent(v)). That is, each segment in I stores the segments that span through its interval, but do not span through the interval of its parent.
Read more about this topic: Segment Tree
Famous quotes containing the words structure and/or description:
“Agnosticism is a perfectly respectable and tenable philosophical position; it is not dogmatic and makes no pronouncements about the ultimate truths of the universe. It remains open to evidence and persuasion; lacking faith, it nevertheless does not deride faith. Atheism, on the other hand, is as unyielding and dogmatic about religious belief as true believers are about heathens. It tries to use reason to demolish a structure that is not built upon reason.”
—Sydney J. Harris (1917–1986)
“As they are not seen on their way down the streams, it is thought by fishermen that they never return, but waste away and die, clinging to rocks and stumps of trees for an indefinite period; a tragic feature in the scenery of the river bottoms worthy to be remembered with Shakespeare’s description of the sea-floor.”
—Henry David Thoreau (1817–1862)