Safe Haskell	Safe-Inferred
Language	GHC2021

Data.SegTree.Primal

Description

Segment Tree

Reference

https://codeforces.com/blog/entry/18051

Synopsis

newtype SegTree mv s a = SegTree {
- getSegTree :: mv s a
}
newSegTree :: (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 :: (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> Int -> m a
pullSegTree :: (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> Int -> m ()
writeSegTree :: (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> Int -> a -> m ()
modifySegTree :: (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> (a -> a) -> Int -> m ()
mappendFromTo :: (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> Int -> Int -> m a
mappendTo :: (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> Int -> m a
mappendAll :: (PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> m a
upperBoundFrom :: (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> Int -> (a -> Bool) -> m Int
lowerBoundTo :: (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> Int -> (a -> Bool) -> m Int
extendToPowerOfTwo :: Int -> Int

Documentation

newtype SegTree mv s a Source #

Constructors

SegTree
Fields getSegTree :: mv s a

newSegTree :: (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 :: (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> Int -> m a Source #

O(1)

pullSegTree :: (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> Int -> m () Source #

writeSegTree :: (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> Int -> a -> m () Source #

O(log n)

modifySegTree :: (Monoid a, PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> (a -> a) -> Int -> m () Source #

O(log n)

mappendFromTo :: (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 :: (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 :: (PrimMonad m, MVector mv a) => SegTree mv (PrimState m) a -> m a Source #

mconcat[a[0],...,a[n-1]]

O(1)

upperBoundFrom Source #

Arguments

:: (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

lowerBoundTo Source #

Arguments

:: (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 0
1