Portability | non-portable (MPTCs, etc - see above) |
---|---|
Stability | experimental |
Maintainer | dastapov@gmail.com |
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