8.2. Static Segment Tree

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 ₁ , , 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 ₊₁ ) is called an EI. For convenience, we also include the intervals ( ˆ ˆ , x ) and [ x ₂ _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 ₊₁ ). We define the interval of an inner node as Int( ) := Int( ₁ ) ˆ Int( ₂ ), where ₁ _, ₂ 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.

Figure 8.1: Example of a segment tree.

Algorithm 8.2: Simple algorithm for answering a stabbing query.

   query(       , q     )   output  S  (     )  if      is inner node  then   if   q    Int(     ₁ )  then  query(     ₁  , q  )  else  query(     ₂  , 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.