Portability | non-portable (MPTCs, etc - see above) |
---|---|

Stability | experimental |

Maintainer | dastapov@gmail.com |

Safe Haskell | Safe-Inferred |

Segment Tree implemented following section 10.3 and 10.4 of

- Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars
Computational Geometry, Algorithms and Applications, Third Edition
(2008) pp 231-237
"Finger trees: a simple general-purpose data structure",
*Journal of Functional Programming*16:2 (2006) pp 197-217. http://www.soi.city.ac.uk/~ross/papers/FingerTree.html

Accumulation of results with monoids following Monoids and Finger Trees,
http:apfelmus.nfshost.com*articles*monoid-fingertree.html

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

- data R v
- data Interval v = Interval {}
- data Boundary
- data STree t a
- fromList :: (Monoid t, Measured (Interval a) t, Ord a) => [(a, a)] -> STree t a
- insert :: (Ord a, Measured (Interval a) t) => STree t a -> Interval a -> STree t a
- queryTree :: (Monoid t, Measured (Interval a) t, Ord a) => STree t a -> a -> t
- countingQuery :: (Measured (Interval a) (Sum b), Ord a) => STree (Sum b) a -> a -> b
- stabbingQuery :: (Measured (Interval a) [Interval a], Ord a) => STree [Interval a] a -> a -> [Interval a]

# Documentation

Extension of the type `v`

that includes plus and minus infinity

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

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.

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)