| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
SegTree
Description
Segment tree
A data structure supporting point updates and range queries on a sequence of monoids. This implementation supports large ranges that do not fit in memory, sometimes called a dynamic or sparse segment tree.
Sources:
The complexities below assume mappend takes O(1) time. Let n = r - l + 1 in all instances below.
SegTree implementable Foldable. Folding over all the elements takes O(n).
Documentation
Instances
| Foldable SegTree Source # | |
Defined in SegTree Methods fold :: Monoid m => SegTree m -> m # foldMap :: Monoid m => (a -> m) -> SegTree a -> m # foldMap' :: Monoid m => (a -> m) -> SegTree a -> m # foldr :: (a -> b -> b) -> b -> SegTree a -> b # foldr' :: (a -> b -> b) -> b -> SegTree a -> b # foldl :: (b -> a -> b) -> b -> SegTree a -> b # foldl' :: (b -> a -> b) -> b -> SegTree a -> b # foldr1 :: (a -> a -> a) -> SegTree a -> a # foldl1 :: (a -> a -> a) -> SegTree a -> a # elem :: Eq a => a -> SegTree a -> Bool # maximum :: Ord a => SegTree a -> a # minimum :: Ord a => SegTree a -> a # | |
| Show a => Show (SegTree a) Source # | |
| NFData a => NFData (SegTree a) Source # | |
emptyST :: Monoid a => (Int, Int) -> SegTree a Source #
Builds a segment tree on range (l, r) where each element is mempty. O(log n).
fromListST :: Monoid a => (Int, Int) -> [a] -> SegTree a Source #
Builds a segment tree on (l, r) where the elements are taken from a list. If the list is shorter than the range, the remaining elements are mempty. O(n).