A segment tree T stores a set S of n intervals on the line. A standard segment tree is a balanced binary search tree over the 2n endpoints of S that are stored at the leavesof T . We use the same notation for both a leaf and the point that it contains. We associate an interval denoted
by range(v) with each node v in T . If v is a leaf then range(v) is the interval [v, v]. If v is an internal node, where w is the leftmost leaf in the subtree rooted by v, and z is the rightmost leaf in the subtree rooted by v, then range(v) = [w, z]. We associate with each node v in T a set S(v) consisting of all segments s in S containing range(v) but not containing range(p(v)). Each node v in T holds a secondary data structure, representing the set S(v).
An interval tree is defined similarly. The difference is that in an interval tree an interval s = (xs, xe) is in S(v) if and only if v is the lowest common ancestor of xs and xe in T . It follows that a segment tree required O(n log n) space and an interval tree requires O(n) space.
by range(v) with each node v in T . If v is a leaf then range(v) is the interval [v, v]. If v is an internal node, where w is the leftmost leaf in the subtree rooted by v, and z is the rightmost leaf in the subtree rooted by v, then range(v) = [w, z]. We associate with each node v in T a set S(v) consisting of all segments s in S containing range(v) but not containing range(p(v)). Each node v in T holds a secondary data structure, representing the set S(v).
An interval tree is defined similarly. The difference is that in an interval tree an interval s = (xs, xe) is in S(v) if and only if v is the lowest common ancestor of xs and xe in T . It follows that a segment tree required O(n log n) space and an interval tree requires O(n) space.
