| Safe Haskell | None |
|---|---|
| Language | GHC2021 |
Data.SegTree.Primal
Description
Synopsis
- newtype SegTree (mv :: k -> k1 -> Type) (s :: k) (a :: k1) = SegTree {
- getSegTree :: mv s a
- newSegTree :: forall a (mv :: Type -> Type -> Type) m. (Monoid a, MVector mv a, PrimMonad m) => Int -> m (SegTree mv (PrimState m) a)
- buildSegTree :: (Monoid a, PrimMonad m, Vector v a) => v a -> m (SegTree (Mutable v) (PrimState m) a)
- readSegTree :: forall a m (mv :: Type -> Type -> Type). (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> Int -> m a
- pullSegTree :: forall a m (mv :: Type -> Type -> Type). (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> Int -> m ()
- writeSegTree :: forall a m (mv :: Type -> Type -> Type). (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> Int -> a -> m ()
- modifySegTree :: forall a m (mv :: Type -> Type -> Type). (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> (a -> a) -> Int -> m ()
- mappendFromTo :: forall a m (mv :: Type -> Type -> Type). (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> Int -> Int -> m a
- mappendTo :: forall a m (mv :: Type -> Type -> Type). (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> Int -> m a
- mappendAll :: forall m (mv :: Type -> Type -> Type) a. (PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> m a
- upperBoundFrom :: forall a m (mv :: Type -> Type -> Type). (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> Int -> (a -> Bool) -> m Int
- lowerBoundTo :: forall a m (mv :: Type -> Type -> Type). (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> Int -> (a -> Bool) -> m Int
- extendToPowerOfTwo :: Int -> Int
Documentation
newtype SegTree (mv :: k -> k1 -> Type) (s :: k) (a :: k1) Source #
Constructors
| SegTree | |
Fields
| |
newSegTree :: forall a (mv :: Type -> Type -> Type) m. (Monoid a, MVector mv a, PrimMonad m) => Int -> m (SegTree mv (PrimState m) a) Source #
>>>import Data.Semigroup (Min)>>>import qualified Data.Vector.Unboxed.Mutable as UM>>>newSegTree @(Min Int) @UM.MVector 123
buildSegTree :: (Monoid a, PrimMonad m, Vector v a) => v a -> m (SegTree (Mutable v) (PrimState m) a) Source #
O(n)
readSegTree :: forall a m (mv :: Type -> Type -> Type). (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> Int -> m a Source #
O(1)
pullSegTree :: forall a m (mv :: Type -> Type -> Type). (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> Int -> m () Source #
writeSegTree :: forall a m (mv :: Type -> Type -> Type). (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> Int -> a -> m () Source #
O(log n)
modifySegTree :: forall a m (mv :: Type -> Type -> Type). (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> (a -> a) -> Int -> m () Source #
O(log n)
mappendFromTo :: forall a m (mv :: Type -> Type -> Type). (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> Int -> Int -> m a Source #
mconcat[a[l],...,a[r-1]]
O(log n)
mappendTo :: forall a m (mv :: Type -> Type -> Type). (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> Int -> m a Source #
mconcat[a[0],...,a[k-1]]
O(log n)
mappendAll :: forall m (mv :: Type -> Type -> Type) a. (PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> m a Source #
mconcat[a[0],...,a[n-1]]
O(1)
Arguments
| :: forall a m (mv :: Type -> Type -> Type). (Monoid a, PrimMonad m, MVector mv a) | |
| => SegTree mv (PrimState m) a | |
| -> Int | left |
| -> (a -> Bool) | predicate s.t. f memepty == True, monotone |
| -> m Int |
max r s.t. f (mappendFromTo seg l r) == True
>>>import Data.Semigroup (Min)>>>import qualified Data.Vector.Unboxed.Mutable as UM>>>seg <- newSegTree @(Min Int) @UM.MVector 10>>>upperBoundFrom seg 0 (const True)16
Arguments
| :: forall a m (mv :: Type -> Type -> Type). (Monoid a, PrimMonad m, MVector mv a) | |
| => SegTree mv (PrimState m) a | |
| -> Int | right |
| -> (a -> Bool) | predicate s.t. f memepty == True, monotone |
| -> m Int |
min l s.t. f (mappendFromTo seg l r) == True
extendToPowerOfTwo :: Int -> Int Source #
>>>extendToPowerOfTwo 01