SegmentTree-0.3: Data structure for querying the set (or count) of intervals covering given point

Portabilitynon-portable (MPTCs, etc - see above)
Safe HaskellSafe-Inferred



Segment Tree implemented following section 10.3 and 10.4 of

Accumulation of results with monoids following Monoids and Finger Trees, http:apfelmus.nfshost.comarticlesmonoid-fingertree.html

An amortized running time is given for each operation, with n referring to the number of intervals.



data R v Source

Extension of the type v that includes plus and minus infinity


R !v 


Bounded (R v) 
Eq v => Eq (R v) 
(Eq (R v), Ord v) => Ord (R v) 
Show v => Show (R v) 

data Interval v Source




ltype :: !Boundary
low :: !(R v)
high :: !(R v)
htype :: !Boundary


Eq v => Eq (Interval v) 
(Eq (Interval v), Ord v) => Ord (Interval v) 
Show v => Show (Interval v) 
(Monoid (Sum b), Num a, Num b) => Measured (Interval a) (Sum b) 
Monoid [Interval a] => Measured (Interval a) [Interval a] 

data Boundary Source

An interval. The lower bound should be less than or equal to the higher bound.




data STree t a Source

Segment Tree is a binary tree that stores Interval in each leaf or branch. By construction (see leaf and branch) intervals in branches should be union of the intervals from left and right subtrees.

Additionally, each node carries a tag of type t (which should be monoid). By supplying different monoids, segment tree could be made to support different types of stabbing queries: Sum or Integer monoid will give tree that counts hits, and list or Set monoids will give a tree that returns actual intervals containing point.


Leaf !t !(Interval a) 
Branch !t !(Interval a) !(STree t a) !(STree t a) 


(Show t, Show a) => Show (STree t a) 

fromList :: (Monoid t, Measured (Interval a) t, Ord a) => [(a, a)] -> STree t aSource

Build the SegmentTree for the given list of pair of points. Time: O(n*log n) Segment tree is built as follows: * Supplied list of point pairs define so-called atomic intervals * They are used to build skeleton binary tree * Each supplied interval is then inserted into this tree, updating tag values in tree branches and leaves

insert :: (Ord a, Measured (Interval a) t) => STree t a -> Interval a -> STree t aSource

Insert interval i into segment tree, updating tag values as necessary. Semantics of tags depends on the monoid used (see fromList)

queryTree :: (Monoid t, Measured (Interval a) t, Ord a) => STree t a -> a -> tSource

Query the segment tree for the specified point. Time: O(log n)

countingQuery :: (Measured (Interval a) (Sum b), Ord a) => STree (Sum b) a -> a -> bSource

Convenience wrapper around queryTree. Returns count of intervals covering the point

stabbingQuery :: (Measured (Interval a) [Interval a], Ord a) => STree [Interval a] a -> a -> [Interval a]Source

Convenience wrapper around queryTree to perform stabbing query. Returns list of intevals coverting the point