| Portability | non-portable (MPTCs, etc - see above) |
|---|---|
| Stability | experimental |
| Maintainer | dastapov@gmail.com |
Data.SegmentTree
Description
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.comarticlesmonoid-fingertree.html
An amortized running time is given for each operation, with n referring to the number of intervals.
- 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
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)
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