| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
SegTreeLazy
Description
Segment tree with lazy propagation
A data structure supporting point updates, range queries, and certain range updates on a sequence of monoids. This differs from an ordinary segment tree in its ability to apply updates on a range, they are otherwise identical. In fact, Segtree a can be defined as LazySegTree () a. This implementation, like SegTree, supports large ranges that may not fit in memory.
Sources:
LazySegTree u a is a segment tree on elements of type a and updates of type u. The instance of
Action u a determines the behavior of the tree. In addition to Action's laws, the segment tree
requires
(x1 <> x2) act u = (x1 act u) <> (x2 act u)
The complexities below assume <> for u, <> for a and act all take O(1) time. Let n = r - l + 1 in all instances below.
Synopsis
- data LazySegTree u a
- emptyLST :: Action u a => (Int, Int) -> LazySegTree u a
- fromListLST :: Action u a => (Int, Int) -> [a] -> LazySegTree u a
- adjustLST :: Action u a => (a -> a) -> Int -> LazySegTree u a -> LazySegTree u a
- updateRangeLST :: Action u a => u -> Int -> Int -> LazySegTree u a -> LazySegTree u a
- foldRangeLST :: Action u a => Int -> Int -> LazySegTree u a -> a
- foldrLST :: Action u a => (a -> b -> b) -> b -> LazySegTree u a -> b
Documentation
data LazySegTree u a Source #
Instances
| (Show a, Show u) => Show (LazySegTree u a) Source # | |
Defined in SegTreeLazy Methods showsPrec :: Int -> LazySegTree u a -> ShowS # show :: LazySegTree u a -> String # showList :: [LazySegTree u a] -> ShowS # | |
| (NFData u, NFData a) => NFData (LazySegTree u a) Source # | |
Defined in SegTreeLazy Methods rnf :: LazySegTree u a -> () # | |
emptyLST :: Action u a => (Int, Int) -> LazySegTree u a Source #
Builds a segment tree on range (l, r) where each element is mempty. O(log n).
fromListLST :: Action u a => (Int, Int) -> [a] -> LazySegTree 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).
adjustLST :: Action u a => (a -> a) -> Int -> LazySegTree u a -> LazySegTree u a Source #
Adjusts the element at index i. O(log n).
updateRangeLST :: Action u a => u -> Int -> Int -> LazySegTree u a -> LazySegTree u a Source #
Applies an update on elements in the range (ql, qr). O(log n).
foldRangeLST :: Action u a => Int -> Int -> LazySegTree u a -> a Source #
Folds the elements in the range (ql, qr). Elements outside (l, r) are considered to be mempty. O(log n).
foldrLST :: Action u a => (a -> b -> b) -> b -> LazySegTree u a -> b Source #
Right fold over the elements of the segment tree. O(n). LazySegTree u cannot be Foldable because of the Action constraint :(