| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
SegTreeLazyMut
Description
Mutable segment tree with lazy propagation
See LazySegTree. LazySegTreeMut is just that, but backed by mutable arrays. When the arrays are unboxed, LazySegTreeMut is a few times faster than LazySegTree (see benchmarks). However, this comes at the cost of purity.
Synopsis
- data LazySegTreeMut marru marra u a
- emptyLSTM :: (Action u a, MArray marru u m, MArray marra a m) => (Int, Int) -> m (LazySegTreeMut marru marra u a)
- fromListLSTM :: (Action u a, MArray marru u m, MArray marra a m) => (Int, Int) -> [a] -> m (LazySegTreeMut marru marra u a)
- adjustLSTM :: (Action u a, MArray marru u m, MArray marra a m) => LazySegTreeMut marru marra u a -> Int -> (a -> a) -> m ()
- updateRangeLSTM :: (Action u a, MArray marru u m, MArray marra a m) => LazySegTreeMut marru marra u a -> Int -> Int -> u -> m ()
- foldRangeLSTM :: (Action u a, MArray marru u m, MArray marra a m) => LazySegTreeMut marru marra u a -> Int -> Int -> m a
- binSearchLSTM :: (Action u a, MArray marru u m, MArray marra a m) => LazySegTreeMut marru marra u a -> Int -> Int -> (a -> Bool) -> m (Maybe (Int, a))
- foldrLSTM :: (Action u a, MArray marru u m, MArray marra a m) => LazySegTreeMut marru marra u a -> (a -> b -> b) -> b -> m b
Documentation
data LazySegTreeMut marru marra u a Source #
emptyLSTM :: (Action u a, MArray marru u m, MArray marra a m) => (Int, Int) -> m (LazySegTreeMut marru marra u a) Source #
Builds a segment tree on range (l, r) where each element is mempty. O(n).
fromListLSTM :: (Action u a, MArray marru u m, MArray marra a m) => (Int, Int) -> [a] -> m (LazySegTreeMut marru marra u 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).
adjustLSTM :: (Action u a, MArray marru u m, MArray marra a m) => LazySegTreeMut marru marra u a -> Int -> (a -> a) -> m () Source #
Adjusts the element at index i. O(log n).
updateRangeLSTM :: (Action u a, MArray marru u m, MArray marra a m) => LazySegTreeMut marru marra u a -> Int -> Int -> u -> m () Source #
Applies an update on elements in the range (ql, qr). O(log n).
foldRangeLSTM :: (Action u a, MArray marru u m, MArray marra a m) => LazySegTreeMut marru marra u a -> Int -> Int -> m a Source #
Folds the elements in the range (ql, qr). Elements outside (l, r) are considered to be mempty. O(log n).
binSearchLSTM :: (Action u a, MArray marru u m, MArray marra a m) => LazySegTreeMut marru marra u a -> Int -> Int -> (a -> Bool) -> m (Maybe (Int, a)) Source #
Binary search in the intersection of (l, r) and (ql, qr) for the shortest prefix whose fold satisfies the given monotonic predicate. Returns the end index and the fold. O(log n).