| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Data.SegmentTree.Beats
Description
Lazily propagated segment tree with interval chmax/chmin.
The internals are almost entirely copy of the Lazy module.
TODO: Do not duplicate code.
Possible queries
Segment tree beats can also handle gcd queries, but it's not considered in this module.
Synopsis
- data SegmentTreeBeats a op s = SegmentTreeBeats !(MVector s a) !(MVector s op) !Int
- newSTBImpl :: (Monoid a, Unbox a, Monoid op, Unbox op, PrimMonad m) => Int -> m (SegmentTreeBeats a op (PrimState m))
- newSTB :: (Unbox a, Monoid a, Monoid op, Unbox op, PrimMonad m) => Int -> m (SegmentTreeBeats a op (PrimState m))
- generateSTBImpl :: (HasCallStack, Monoid a, Unbox a, Monoid op, Unbox op, PrimMonad m) => Int -> (Int -> a) -> m (SegmentTreeBeats a op (PrimState m))
- generateSTB :: (HasCallStack, Unbox a, Monoid a, Monoid op, Unbox op, PrimMonad m) => Int -> (Int -> a) -> m (SegmentTreeBeats a op (PrimState m))
- buildSTB :: (HasCallStack, Unbox a, Monoid a, Monoid op, Unbox op, PrimMonad m) => Vector a -> m (SegmentTreeBeats a op (PrimState m))
- foldSTB :: forall a op m. (HasCallStack, FailableSemigroupActionTarget a, Monoid a, Eq a, Unbox a, Monoid op, SegmentAction op a, Eq op, Unbox op, PrimMonad m) => SegmentTreeBeats a op (PrimState m) -> Int -> Int -> m a
- foldMaySTB :: (HasCallStack, FailableSemigroupActionTarget a, Monoid a, Eq a, Unbox a, Monoid op, SegmentAction op a, Eq op, Unbox op, PrimMonad m) => SegmentTreeBeats a op (PrimState m) -> Int -> Int -> m (Maybe a)
- readSTB :: (HasCallStack, FailableSemigroupActionTarget a, Monoid a, Eq a, Unbox a, Monoid op, SegmentAction op a, Eq op, Unbox op, PrimMonad m) => SegmentTreeBeats a op (PrimState m) -> Int -> m a
- foldAllSTB :: (HasCallStack, FailableSemigroupActionTarget a, Eq a, Monoid a, Unbox a, Monoid op, SegmentAction op a, Eq op, Unbox op, PrimMonad m) => SegmentTreeBeats a op (PrimState m) -> m a
- sactSTB :: forall a op m. (FailableSemigroupActionTarget a, Monoid a, Eq a, Unbox a, Monoid op, SegmentAction op a, Eq op, Unbox op, PrimMonad m) => SegmentTreeBeats a op (PrimState m) -> Int -> Int -> op -> m ()
- sactAtSTB :: (FailableSemigroupActionTarget a, Monoid a, Eq a, Unbox a, Monoid op, SegmentAction op a, Eq op, Unbox op, PrimMonad m) => SegmentTreeBeats a op (PrimState m) -> Int -> op -> m ()
- _propDownFromRootSTB :: (HasCallStack, FailableSemigroupActionTarget a, Monoid a, Eq a, Unbox a, Monoid op, SegmentAction op a, Eq op, Unbox op, PrimMonad m) => SegmentTreeBeats a op (PrimState m) -> Int -> Int -> m ()
- _sactAtSTB :: (HasCallStack, FailableSemigroupActionTarget a, Semigroup a, Eq a, Unbox a, Monoid op, Eq op, SegmentAction op a, Unbox op, PrimMonad m) => SegmentTreeBeats a op (PrimState m) -> Int -> op -> m ()
- _propAt :: (HasCallStack, FailableSemigroupActionTarget a, Semigroup a, Eq a, Unbox a, Monoid op, Eq op, SegmentAction op a, Unbox op, PrimMonad m) => SegmentTreeBeats a op (PrimState m) -> Int -> m ()
- bisectSTB :: (HasCallStack, FailableSemigroupActionTarget a, Monoid a, Eq a, Unbox a, Monoid op, SegmentAction op a, Eq op, Unbox op, PrimMonad m) => SegmentTreeBeats a op (PrimState m) -> Int -> Int -> (a -> Bool) -> m (Maybe Int, Maybe Int)
- bisectSTBL :: (HasCallStack, FailableSemigroupActionTarget a, Monoid a, Eq a, Unbox a, Monoid op, SegmentAction op a, Eq op, Unbox op, PrimMonad m) => SegmentTreeBeats a op (PrimState m) -> Int -> Int -> (a -> Bool) -> m (Maybe Int)
- bisectSTBR :: (HasCallStack, FailableSemigroupActionTarget a, Monoid a, Eq a, Unbox a, Monoid op, SegmentAction op a, Eq op, Unbox op, PrimMonad m) => SegmentTreeBeats a op (PrimState m) -> Int -> Int -> (a -> Bool) -> m (Maybe Int)
Documentation
data SegmentTreeBeats a op s #
Segment tree beats
Constructors
| SegmentTreeBeats !(MVector s a) !(MVector s op) !Int |
newSTBImpl :: (Monoid a, Unbox a, Monoid op, Unbox op, PrimMonad m) => Int -> m (SegmentTreeBeats a op (PrimState m)) #
\(O(N)\) Creates a SegmentTreeBeats with mempty as the initial accumulated values.
newSTB :: (Unbox a, Monoid a, Monoid op, Unbox op, PrimMonad m) => Int -> m (SegmentTreeBeats a op (PrimState m)) #
\(O(N)\)
generateSTBImpl :: (HasCallStack, Monoid a, Unbox a, Monoid op, Unbox op, PrimMonad m) => Int -> (Int -> a) -> m (SegmentTreeBeats a op (PrimState m)) #
\(O(N)\) Creates SegmentTreeBeats with initial leaf values.
generateSTB :: (HasCallStack, Unbox a, Monoid a, Monoid op, Unbox op, PrimMonad m) => Int -> (Int -> a) -> m (SegmentTreeBeats a op (PrimState m)) #
\(O(N)\)
buildSTB :: (HasCallStack, Unbox a, Monoid a, Monoid op, Unbox op, PrimMonad m) => Vector a -> m (SegmentTreeBeats a op (PrimState m)) #
\(O(N)\). TODO: Share the internal implementation with genearteSTB takeing filling function.
Action with length given by the segment tree
foldSTB :: forall a op m. (HasCallStack, FailableSemigroupActionTarget a, Monoid a, Eq a, Unbox a, Monoid op, SegmentAction op a, Eq op, Unbox op, PrimMonad m) => SegmentTreeBeats a op (PrimState m) -> Int -> Int -> m a #
\(O(\log N)\)
foldMaySTB :: (HasCallStack, FailableSemigroupActionTarget a, Monoid a, Eq a, Unbox a, Monoid op, SegmentAction op a, Eq op, Unbox op, PrimMonad m) => SegmentTreeBeats a op (PrimState m) -> Int -> Int -> m (Maybe a) #
\(O(\log N)\)
readSTB :: (HasCallStack, FailableSemigroupActionTarget a, Monoid a, Eq a, Unbox a, Monoid op, SegmentAction op a, Eq op, Unbox op, PrimMonad m) => SegmentTreeBeats a op (PrimState m) -> Int -> m a #
\(O(\log N)\) Read one leaf. TODO: Faster implementation.
foldAllSTB :: (HasCallStack, FailableSemigroupActionTarget a, Eq a, Monoid a, Unbox a, Monoid op, SegmentAction op a, Eq op, Unbox op, PrimMonad m) => SegmentTreeBeats a op (PrimState m) -> m a #
\(O(\log N)\)
sactSTB :: forall a op m. (FailableSemigroupActionTarget a, Monoid a, Eq a, Unbox a, Monoid op, SegmentAction op a, Eq op, Unbox op, PrimMonad m) => SegmentTreeBeats a op (PrimState m) -> Int -> Int -> op -> m () #
\(O(\log N)\) Applies a lazy operator monoid over an interval, propagated lazily.
sactAtSTB :: (FailableSemigroupActionTarget a, Monoid a, Eq a, Unbox a, Monoid op, SegmentAction op a, Eq op, Unbox op, PrimMonad m) => SegmentTreeBeats a op (PrimState m) -> Int -> op -> m () #
\(O(\log N)\) Acts on one leaf. TODO: Specialize the implementation.
_propDownFromRootSTB :: (HasCallStack, FailableSemigroupActionTarget a, Monoid a, Eq a, Unbox a, Monoid op, SegmentAction op a, Eq op, Unbox op, PrimMonad m) => SegmentTreeBeats a op (PrimState m) -> Int -> Int -> m () #
\(O(\log N)\) Propagates the lazy operator monoids from the root to just before the glitch segments.
iLeaf: Given with zero-based index.
Pruning
The propagation is performed from the root to just before the folded vertices. In other words, propagation is performed just before performing the first glitch. That's enough for both folding and acting.
_sactAtSTB :: (HasCallStack, FailableSemigroupActionTarget a, Semigroup a, Eq a, Unbox a, Monoid op, Eq op, SegmentAction op a, Unbox op, PrimMonad m) => SegmentTreeBeats a op (PrimState m) -> Int -> op -> m () #
\(O(1)\) Acts on a node.
Evaluation strategy
- The propagated value for the children are stored and propagated lazily.
- The propagated value to the vertex is evaluated instantly.
Invariants
- The new coming operator operator always comes from the left.
_propAt :: (HasCallStack, FailableSemigroupActionTarget a, Semigroup a, Eq a, Unbox a, Monoid op, Eq op, SegmentAction op a, Unbox op, PrimMonad m) => SegmentTreeBeats a op (PrimState m) -> Int -> m () #
Propagates the operator onto the children. Push.
Bisection methods
bisectSTB :: (HasCallStack, FailableSemigroupActionTarget a, Monoid a, Eq a, Unbox a, Monoid op, SegmentAction op a, Eq op, Unbox op, PrimMonad m) => SegmentTreeBeats a op (PrimState m) -> Int -> Int -> (a -> Bool) -> m (Maybe Int, Maybe Int) #
\(O(\log^2 N)\) The l, r indices are the zero-based leaf indices.
bisectSTBL :: (HasCallStack, FailableSemigroupActionTarget a, Monoid a, Eq a, Unbox a, Monoid op, SegmentAction op a, Eq op, Unbox op, PrimMonad m) => SegmentTreeBeats a op (PrimState m) -> Int -> Int -> (a -> Bool) -> m (Maybe Int) #
\(O(\log^2 N)\)
bisectSTBR :: (HasCallStack, FailableSemigroupActionTarget a, Monoid a, Eq a, Unbox a, Monoid op, SegmentAction op a, Eq op, Unbox op, PrimMonad m) => SegmentTreeBeats a op (PrimState m) -> Int -> Int -> (a -> Bool) -> m (Maybe Int) #
\(O(\log^2 N)\)