![]() | ||
| ||
![]() |
This is a quick recap, so if you are familiar with this classic data structure, you can proceed to the next section.
Given a set S ={ s 1 , , s n } of intervals s i = [ a i , b i ] , and a query point q ˆˆ
, we are looking for the subset S ={ s ˆˆ S q ˆˆ s }. This is often called a stabbing query and can be extended trivially to
d .
Before describing the data structure, we define an elementary interval (EI). Let X = { a, b a ˆˆ s ˆˆ S, b ˆˆ s ˆˆ S } = { x i } denote the set of endpoints , sorted by increasing value in a list. Then the interval [ x i , x i +1 ) is called an EI. For convenience, we also include the intervals ( ˆ ˆ , x ) and [ x 2 n , ˆ ).
The segment tree is a balanced binary tree over the set of EIs, X . Each leaf i stores one EI Int( i ) := [ x i , x i +1 ). We define the interval of an inner node as Int( ) := Int( 1 ) ˆ Int( 2 ), where 1 , 2 are the two children of . Each node stores the so-called canonical subset S ( ) := { s ˆˆ S Int( ) s, Int(parent( )) s} (in other words, each interval s ˆˆ S is stored with several nodes k in the tree, such that
k Int( k ) = s , and such that s is stored as high up as possible). An example is shown in Figure 8.1.
|
query( , q ) output S ( ) if is inner node then if q Int( 1 ) then query( 1 , q ) else query( 2 , q ) end if end if
|
The construction of a segment tree is very easy: generate and sort X ; construct a skeleton binary tree over 2 n + 1 nodes; compute Int( ) for all nodes in the tree; and sift each segment s top-down through the tree.
The algorithm for answering a stabbing query is quite simple, as shown in Algorithm 8.2.
It is easy to see that such a segment tree needs O ( n log n ) space and O ( n log n ) construction time, and that a query can be answered in time O (log n + k ), where k is the size of the output.