ac-library-hs-1.2.1.0: Data structures and algorithms
Safe HaskellSafe-Inferred
LanguageGHC2021

AtCoder.Extra.DynSparseSegTree.Raw

Description

Base module of a dynamic, sparse segment tree.

Since: 1.2.1.0

Synopsis

Dynamic, sparse segment tree

data DynSparseSegTree s a Source #

A dynamic, sparse segment tree that covers a half-open interval \([l_0, r_0)\). Is is dynamic in that the nodes are instantinated as needed.

Since: 1.2.1.0

Constructors

DynSparseSegTree 

Fields

  • capacityDsst :: !Int

    The maximum number of nodes allocated

    Since: 1.2.1.0

  • isPersistentDsst :: !Bool

    Whether the data is persistent or not

    Since: 1.2.1.0

  • l0Dsst :: !Int

    Left index boundary (inclusive)

    Since: 1.2.1.0

  • r0Dsst :: !Int

    Right index boundary (exclusive)

    Since: 1.2.1.0

  • poolDsst :: !(Pool s ())

    Pool for free slot management.

    Since: 1.2.1.0

  • lDsst :: !(MVector s Index)

    Decomposed node storage: left children

    Since: 1.2.1.0

  • rDsst :: !(MVector s Index)

    Decomposed node storage: right children

    Since: 1.2.1.0

  • xDsst :: !(MVector s a)

    Decomposed node storage: position

    Since: 1.2.1.0

  • iDsst :: !(MVector s Int)

    Decomposed node storage: position

    Since: 1.2.1.0

  • prodDsst :: !(MVector s a)

    Decomposed node storage: monoid product

    Since: 1.2.1.0

Re-exports

newtype Index Source #

Strongly typed index of pool items. User has to explicitly corece on raw index use.

Constructors

Index 

Fields

Instances

Instances details
Show Index Source # 
Instance details

Defined in AtCoder.Extra.Pool

Methods

showsPrec :: Int -> Index -> ShowS #

show :: Index -> String #

showList :: [Index] -> ShowS #

Eq Index Source # 
Instance details

Defined in AtCoder.Extra.Pool

Methods

(==) :: Index -> Index -> Bool #

(/=) :: Index -> Index -> Bool #

Ord Index Source # 
Instance details

Defined in AtCoder.Extra.Pool

Methods

compare :: Index -> Index -> Ordering #

(<) :: Index -> Index -> Bool #

(<=) :: Index -> Index -> Bool #

(>) :: Index -> Index -> Bool #

(>=) :: Index -> Index -> Bool #

max :: Index -> Index -> Index #

min :: Index -> Index -> Index #

Prim Index Source # 
Instance details

Defined in AtCoder.Extra.Pool

Methods

sizeOfType# :: Proxy Index -> Int# #

sizeOf# :: Index -> Int# #

alignmentOfType# :: Proxy Index -> Int# #

alignment# :: Index -> Int# #

indexByteArray# :: ByteArray# -> Int# -> Index #

readByteArray# :: MutableByteArray# s -> Int# -> State# s -> (# State# s, Index #) #

writeByteArray# :: MutableByteArray# s -> Int# -> Index -> State# s -> State# s #

setByteArray# :: MutableByteArray# s -> Int# -> Int# -> Index -> State# s -> State# s #

indexOffAddr# :: Addr# -> Int# -> Index #

readOffAddr# :: Addr# -> Int# -> State# s -> (# State# s, Index #) #

writeOffAddr# :: Addr# -> Int# -> Index -> State# s -> State# s #

setOffAddr# :: Addr# -> Int# -> Int# -> Index -> State# s -> State# s #

Unbox Index Source # 
Instance details

Defined in AtCoder.Extra.Pool

Vector Vector Index Source # 
Instance details

Defined in AtCoder.Extra.Pool

Methods

basicUnsafeFreeze :: Mutable Vector s Index -> ST s (Vector Index)

basicUnsafeThaw :: Vector Index -> ST s (Mutable Vector s Index)

basicLength :: Vector Index -> Int

basicUnsafeSlice :: Int -> Int -> Vector Index -> Vector Index

basicUnsafeIndexM :: Vector Index -> Int -> Box Index

basicUnsafeCopy :: Mutable Vector s Index -> Vector Index -> ST s ()

elemseq :: Vector Index -> Index -> b -> b

MVector MVector Index Source # 
Instance details

Defined in AtCoder.Extra.Pool

Methods

basicLength :: MVector s Index -> Int

basicUnsafeSlice :: Int -> Int -> MVector s Index -> MVector s Index

basicOverlaps :: MVector s Index -> MVector s Index -> Bool

basicUnsafeNew :: Int -> ST s (MVector s Index)

basicInitialize :: MVector s Index -> ST s ()

basicUnsafeReplicate :: Int -> Index -> ST s (MVector s Index)

basicUnsafeRead :: MVector s Index -> Int -> ST s Index

basicUnsafeWrite :: MVector s Index -> Int -> Index -> ST s ()

basicClear :: MVector s Index -> ST s ()

basicSet :: MVector s Index -> Index -> ST s ()

basicUnsafeCopy :: MVector s Index -> MVector s Index -> ST s ()

basicUnsafeMove :: MVector s Index -> MVector s Index -> ST s ()

basicUnsafeGrow :: MVector s Index -> Int -> ST s (MVector s Index)

newtype Vector Index Source # 
Instance details

Defined in AtCoder.Extra.Pool

newtype Vector Index = V_Index (Vector Index)
newtype MVector s Index Source # 
Instance details

Defined in AtCoder.Extra.Pool

newtype MVector s Index = MV_Index (MVector s Index)

Constructors

newST :: (HasCallStack, Unbox a) => Bool -> Int -> Int -> Int -> ST s (DynSparseSegTree s a) Source #

\(O(n)\)

Since: 1.2.1.0

newRootST :: (HasCallStack, Monoid a, Unbox a) => DynSparseSegTree s a -> ST s Index Source #

\(O(1)\)

Since: 1.2.1.0

newNodeST :: (HasCallStack, Monoid a, Unbox a) => DynSparseSegTree s a -> Int -> a -> ST s Index Source #

\(O(1)\)

Since: 1.2.1.0

freeSubtreeST :: (HasCallStack, Monoid a, Unbox a) => DynSparseSegTree s a -> Index -> ST s () Source #

\(O(n)\)

Since: 1.2.1.0

Accessing elements

modifyMST :: forall m a. (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DynSparseSegTree (PrimState m) a -> Index -> (a -> m a) -> Int -> m Index Source #

\(O(\log L)\)

Since: 1.2.1.0

Products

prodST :: forall a s. (HasCallStack, Monoid a, Unbox a) => DynSparseSegTree s a -> Index -> Int -> Int -> ST s a Source #

\(O(\log L)\)

Since: 1.2.1.0

Binary searches

maxRightM :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DynSparseSegTree (PrimState m) a -> Index -> (a -> m Bool) -> m Int Source #

\(O(\log L)\)

Constraints

  • The segment tree is not empty
  • User predicate \(f\) returns True for mempty

Since: 1.2.1.0