| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
SegTreeMut
Description
Mutable segment tree
See SegTree. SegTreeMut is just that, but backed by a mutable array. With unboxed arrays, SegTreeMut is multiple times faster than SegTree (see benchmarks). However, this comes at the cost of purity.
Sources:
- Al.Cash, "Efficient and easy segment trees" https://codeforces.com/blog/entry/18051
- AtCoder Library https://github.com/atcoder/ac-library/blob/master/atcoder/segtree.hpp
Let n = r - l + 1 where (l, r) is the range of the segment tree. The complexities assume (<>) takes O(1) time.
Synopsis
- data SegTreeMut marr a
- emptySTM :: (Monoid a, MArray marr a m) => (Int, Int) -> m (SegTreeMut marr a)
- fromListSTM :: (Monoid a, MArray marr a m) => (Int, Int) -> [a] -> m (SegTreeMut marr a)
- adjustSTM :: (Monoid a, MArray marr a m) => SegTreeMut marr a -> Int -> (a -> a) -> m ()
- foldRangeSTM :: (Monoid a, MArray marr a m) => SegTreeMut marr a -> Int -> Int -> m a
- binSearchSTM :: (Monoid a, MArray marr a m) => SegTreeMut marr a -> Int -> Int -> (a -> Bool) -> m (Maybe (Int, a))
- foldrSTM :: (Monoid a, MArray marr a m) => SegTreeMut marr a -> (a -> b -> b) -> b -> m b
Documentation
data SegTreeMut marr a Source #
emptySTM :: (Monoid a, MArray marr a m) => (Int, Int) -> m (SegTreeMut marr a) Source #
Builds a segment tree on (l, r) where each element is mempty. O(n).
fromListSTM :: (Monoid a, MArray marr a m) => (Int, Int) -> [a] -> m (SegTreeMut marr 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).
adjustSTM :: (Monoid a, MArray marr a m) => SegTreeMut marr a -> Int -> (a -> a) -> m () Source #
Adjusts the element at index i. O(log n).
foldRangeSTM :: (Monoid a, MArray marr a m) => SegTreeMut marr 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), or more precisely O(log(min(r, qr) - max(l, ql) + 1)).
binSearchSTM :: (Monoid a, MArray marr a m) => SegTreeMut marr 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), or more precisely O(log(min(r, qr) - max(l, ql) + 1)).