Segment Trees
[Bentley]
A segment tree is a data structure for storing a set of intervals
I = {[x1 , x10 ], [x2 , x20 ], . . . , [xn , xn0 ]}
and can be used for solving problems e.g. concerning line segments.
Let p1 , . . . , pm , m ≤ 2n, be the ordered list of distinct endpoints of
the intervals in I. The ordered sequence of endpoints p1 , . . . , pm par-
titions the real line into a set of atomic intervals
(−∞, p1 ), [p1 , p1 ], (p1 , p2 ), [p2 , p2 ], . . . , (pn−1 , pn ), [pn , pn ], (pn , ∞)
1
A segment tree is a balanced tree where each node corresponds to an
interval. The leaves correspond to the atomic intervals according to
left to right order. An internal node u corresponds to the union of the
intervals corresponding to the leaves of the subtree rooted at u.
2
Let int(v) denote the interval corresponding to node v. With each
node v we store a set I(v) ⊆ I: Interval [x, x0 ] is stored in I(v) if and
only if
int(v) ⊆ [x, x0 ] and int(parent(v)) 6⊆ [x, x0 ]
Lemma: A segment tree on n intervals uses O(n log n) storage.
An interval is stored with at most two nodes at the same depth of the tree.
3
I NSERT S EGMENT T REE(v, [x, x0 ])
1 if int(v) ⊆ [x, x0 ]
2 then add [x, x0 ] to I(v)
3 else if int(lc(v)) ∩ [x, x0 ] 6= 0/
4 then I NSERT S EGMENT T REE(lc(v), [x, x0 ])
5 if int(rc(v)) ∩ [x, x0 ] 6= 0/
6 then I NSERT S EGMENT T REE(rc(v), [x, x0 ])
Lemma: A segment tree for a set of n intervals can be constructed
in O(n log n) time.
4
5
Q UERY S EGMENT T REE(v, qx )
1 Report all the intervals in I(v)
2 if v is not a leaf
3 then if qx ∈ int(lc(v))
4 then Q UERY S EGMENT T REE(lc(v), qx )
5 else Q UERY S EGMENT T REE(rc(v), qx )
Lemma: Using a segment tree, we can report all k intervals that
contain a query point qx , in time O(k + log n).
6
Vertical stabbing queries in a set of disjoint line segments
Let S be a set of pairwise dis-
joint line segments in the plane.
We want to maintain S in a
data structure that allows us to
quickly find the segments inter-
sected by a vertical query seg-
ment
qx × [qy , q0y ]
Store S in a segment tree based on the x-intervals of the segments.
7
For a node v, let S(v) be the set of segments corresponding to the
intervals in I(v).
Store the segments in S(v) in an associated balanced binary search
tree based on the order of the elements in the slab int(v) × (−∞, ∞).
If segments are horizontal, we get a segment-range tree.
8
Lemma: Let S be a set of n disjoint segments in the plane. S can
be stored in a data structure such that the segments in S intersected
by a vertical query segment can be reported in time O(k + (log n)2 ),
where k is the number of reported segments. The data structure uses
O(n log n) storage space and can be built in O(n(log n)2 ) time.
Construction time can be improved to O(n log n).
9
Semi-static Segment Trees
Let X be a set of N real numbers. We construct a balanced binary
search tree on the atomic intervals defined by these numbers.
Now we can insert and delete intervals with endpoints in X. Insertion
takes time O(log N). Deletion of an interval s takes time O(log N) as
well, if we know the positions of s in all sets I(v) where s is stored.
10
Klee’s Measure Problem
Given a collection of intervals, what is the length of their union?
Given a collection of axis-aligned
rectangles, what is the area of their
union?
Use plane-sweep and maintain the
intersection of the rectangles and
the sweep line in a (semi-static)
segment tree. [Bentley]
c Jeff Erickson
Theorem: The area of the union of n axis-aligned rectangles in the
plane can be computed in O(n log n) time.
http://granmapa.cs.uiuc.edu/~jeffe/open/klee.html
11
Higher-dimensional Segment Trees
Analogously to range trees, segment trees can be extended to higher
dimensions, for example, in order to solve point enclosure problems
for axis-aligned rectangular boxes. Such point enclosure problems
are also called “inverse range queries”.
12
A d-dimensional segment tree for axis-aligned rectangular boxes in
Rd is an augmented one-dimensional segment tree for the atomic
intervals according to the first dimension.
The secondary data structure associated with a node v is a (d − 1)-
dimensional segment tree according to the remaining coordinates for
the boxes corresponding to the intervals stored at v. More precisely,
it is a (d − 1)-dimensional segment tree for the boxes formed by the
remaining (d − 1) coordinates.
13
Theorem: A d-dimensional segment tree for a set of n axis-aligned
rectangular boxes in Rd can be built in O(n(log n)d ) time and takes
O(n(log n)d ) space.
Theorem: Using a d-dimensional segment tree, point enclosure que-
ries for a set of n axis-aligned rectangular boxes in Rd can be an-
swered in time O(k + (log n)d ) time, where k is the number of re-
ported boxes.
14
