Safe Haskell	Safe-Inferred
Language	GHC2021

Data.SegTree

Synopsis

class (Monoid f, Semigroup s) => AsSemigroupEndo f s where
- sendo :: f -> s -> s
data SegTree s f a = SegTree {
- getSegTree :: !(MVector s a)
- getDualSegTree :: !(MVector s f)
- sizeSegTree :: !Int
- heightSegTree :: !Int
}
newSegTree :: (Monoid f, Unbox f, Monoid a, Unbox a, PrimMonad m) => Int -> m (SegTree (PrimState m) f a)
buildSegTree :: (Monoid f, Unbox f, Monoid a, Unbox a, PrimMonad m) => Vector a -> m (SegTree (PrimState m) f a)
readSegTree :: (AsSemigroupEndo f a, Unbox f, Unbox a, PrimMonad m) => SegTree (PrimState m) f a -> Int -> m a
writeSegTree :: (AsSemigroupEndo f a, Semigroup a, Unbox a, Unbox f, PrimMonad m) => SegTree (PrimState m) f a -> Int -> a -> m ()
modifySegTree :: (AsSemigroupEndo f a, Semigroup a, Unbox f, Unbox a, PrimMonad m) => SegTree (PrimState m) f a -> (a -> a) -> Int -> m ()
mappendFromTo :: (AsSemigroupEndo f a, Monoid a, Unbox f, Unbox a, PrimMonad m) => SegTree (PrimState m) f a -> Int -> Int -> m a
mappendTo :: (AsSemigroupEndo f a, Monoid a, Unbox f, Unbox a, PrimMonad m) => SegTree (PrimState m) f a -> Int -> m a
mappendAll :: (Unbox a, PrimMonad m) => SegTree (PrimState m) f a -> m a
appAt :: (AsSemigroupEndo f a, Semigroup a, Unbox f, Unbox a, PrimMonad m) => SegTree (PrimState m) f a -> Int -> f -> m ()
appFromTo :: (AsSemigroupEndo f a, Semigroup a, Unbox f, Unbox a, PrimMonad m) => SegTree (PrimState m) f a -> Int -> Int -> f -> m ()
upperBoundFrom :: (AsSemigroupEndo f a, Monoid a, Unbox f, Unbox a, PrimMonad m) => SegTree (PrimState m) f a -> Int -> (a -> Bool) -> m Int
lowerBoundTo :: (AsSemigroupEndo f a, Monoid a, Unbox f, Unbox a, PrimMonad m) => SegTree (PrimState m) f a -> Int -> (a -> Bool) -> m Int
evalAt :: (AsSemigroupEndo f a, Unbox f, Unbox a, PrimMonad m) => SegTree (PrimState m) f a -> Int -> f -> m ()
pushSegTree :: (AsSemigroupEndo f a, Unbox f, Unbox a, PrimMonad m) => SegTree (PrimState m) f a -> Int -> m ()
pullSegTree :: (Semigroup a, Unbox a, PrimMonad m) => SegTree (PrimState m) f a -> Int -> m ()
extendToPowerOfTwo :: Int -> Int

Documentation

class (Monoid f, Semigroup s) => AsSemigroupEndo f s where Source #

sendo is a monoid homomorphism (left monoid action)
sendo f is a semigroup endomorphism

Methods

sendo :: f -> s -> s Source #

Instances

Instances details

(Ord a, Bounded a) => AsSemigroupEndo (Max a) (Max a) Source #
Instance details Defined in Data.SegTree.RangeMaxRangeMax Methods sendo :: Max a -> Max a -> Max a Source #
(Ord a, Bounded a) => AsSemigroupEndo (Min a) (Min a) Source #
Instance details Defined in Data.SegTree.RangeMinRangeMin Methods sendo :: Min a -> Min a -> Min a Source #
Num a => AsSemigroupEndo (Dual (Product a)) (Sum a) Source #
Instance details Defined in Data.SegTree.RangeMulRangeSum Methods sendo :: Dual (Product a) -> Sum a -> Sum a Source #
(Ord a, Bounded a) => AsSemigroupEndo (Dual (LastMax a)) (Max a) Source #
Instance details Defined in Data.SegTree.RangeUpdateRangeMax Methods sendo :: Dual (LastMax a) -> Max a -> Max a Source #
(Ord a, Bounded a) => AsSemigroupEndo (Dual (LastMin a)) (Min a) Source #
Instance details Defined in Data.SegTree.RangeUpdateRangeMin Methods sendo :: Dual (LastMin a) -> Min a -> Min a Source #
(Num a, Ord a, Bounded a) => AsSemigroupEndo (Sum a) (Max a) Source #
Instance details Defined in Data.SegTree.RangeAddRangeMax Methods sendo :: Sum a -> Max a -> Max a Source #
(Num a, Ord a, Bounded a) => AsSemigroupEndo (Sum a) (Min a) Source #
Instance details Defined in Data.SegTree.RangeAddRangeMin Methods sendo :: Sum a -> Min a -> Min a Source #
Num a => AsSemigroupEndo (Sum a) (RangedSum a) Source #
Instance details Defined in Data.SegTree.RangeAddRangeSum Methods sendo :: Sum a -> RangedSum a -> RangedSum a Source #
Num a => AsSemigroupEndo (Affine a) (RangedSum a) Source #
Instance details Defined in Data.SegTree.RangeAffineRangeSum Methods sendo :: Affine a -> RangedSum a -> RangedSum a Source #

data SegTree s f a Source #

Constructors

SegTree
Fields getSegTree :: !(MVector s a) getDualSegTree :: !(MVector s f) sizeSegTree :: !Int heightSegTree :: !Int

newSegTree :: (Monoid f, Unbox f, Monoid a, Unbox a, PrimMonad m) => Int -> m (SegTree (PrimState m) f a) Source #

buildSegTree :: (Monoid f, Unbox f, Monoid a, Unbox a, PrimMonad m) => Vector a -> m (SegTree (PrimState m) f a) Source #

O(n)

readSegTree :: (AsSemigroupEndo f a, Unbox f, Unbox a, PrimMonad m) => SegTree (PrimState m) f a -> Int -> m a Source #

O(log n)

writeSegTree :: (AsSemigroupEndo f a, Semigroup a, Unbox a, Unbox f, PrimMonad m) => SegTree (PrimState m) f a -> Int -> a -> m () Source #

O(log n)

modifySegTree :: (AsSemigroupEndo f a, Semigroup a, Unbox f, Unbox a, PrimMonad m) => SegTree (PrimState m) f a -> (a -> a) -> Int -> m () Source #

O(log n)

mappendFromTo :: (AsSemigroupEndo f a, Monoid a, Unbox f, Unbox a, PrimMonad m) => SegTree (PrimState m) f a -> Int -> Int -> m a Source #

mappend [l..r) O(log n)

mappendTo :: (AsSemigroupEndo f a, Monoid a, Unbox f, Unbox a, PrimMonad m) => SegTree (PrimState m) f a -> Int -> m a Source #

mappend [0..k) O(log n)

mappendAll :: (Unbox a, PrimMonad m) => SegTree (PrimState m) f a -> m a Source #

mappend [0..n) O(1)

appAt :: (AsSemigroupEndo f a, Semigroup a, Unbox f, Unbox a, PrimMonad m) => SegTree (PrimState m) f a -> Int -> f -> m () Source #

modify f k O(log n)

appFromTo :: (AsSemigroupEndo f a, Semigroup a, Unbox f, Unbox a, PrimMonad m) => SegTree (PrimState m) f a -> Int -> Int -> f -> m () Source #

mapM_ (modify f) [l..r) O(log n)

upperBoundFrom Source #

Arguments

:: (AsSemigroupEndo f a, Monoid a, Unbox f, Unbox a, PrimMonad m)
=> SegTree (PrimState m) f a
-> Int	left
-> (a -> Bool)	predicate s.t. f memepty == True, monotone
-> m Int

max r s.t. f (mappendFromTo seg l r) == True

lowerBoundTo Source #

Arguments

:: (AsSemigroupEndo f a, Monoid a, Unbox f, Unbox a, PrimMonad m)
=> SegTree (PrimState m) f a
-> Int	right
-> (a -> Bool)	predicate s.t. f memepty == True, monotone
-> m Int

min l s.t. f (mappendFromTo seg l r) == True

evalAt :: (AsSemigroupEndo f a, Unbox f, Unbox a, PrimMonad m) => SegTree (PrimState m) f a -> Int -> f -> m () Source #

O(1)

pushSegTree :: (AsSemigroupEndo f a, Unbox f, Unbox a, PrimMonad m) => SegTree (PrimState m) f a -> Int -> m () Source #

O(1)

pullSegTree :: (Semigroup a, Unbox a, PrimMonad m) => SegTree (PrimState m) f a -> Int -> m () Source #

O(1)

extendToPowerOfTwo :: Int -> Int Source #