 
container Data.
 
 
container Window.
 
 
class Traits.

 
A segment tree is defined, such that the subtree of each
vertex is of the same type prototype
sublayer_tree is. We assume that the dimension of the tree is $$d. This means, that sublayer_tree is a prototype of a $$d1dimensional tree. All data items of the $$ddimensional segment tree have container type Data. The query window of the tree has container type Window. Traits provides access to the corresponding data slots of container Data and Window for the $$dth dimension. The traits class Traits must at least provide all functions and type definitions described, for example, in the reference page for tree_point_traits. The template class described there is fully generic and should fulfill the most requirements one can have. In order to generate a onedimensional segment tree instantiate Tree_anchor<Data, Window> sublayer_tree with the same template parameters Data and Window Segment_tree_d is defined. In order to construct a twodimensional segment tree, create Segment_tree_d with a onedimensional Segment_tree_d with the corresponding Traits of the first dimension. Precondition: Traits::Data==Data and Traits::Window==Window.


 
The tree is constructed according to the data items in the sequence between the element pointed by iterator first and iterator last. 
Protected Operations

 
returns true, if the interval of object is contained in the interval of win. False otherwise.  

 returns false. 
A $$ddimensional segment tree is constructed in $$O(nlog$$n^{d}) time. An inverse range query is performed in time $$O(k+log$$^{d} n ), where $$k is the number of reported intervals. The tree uses $$O(nlog$$n^{d}) storage.