Safe Haskell	Safe-Inferred
Language	GHC2021

Data.SparseTable

Synopsis

type RMQ a = SparseTable Min a
buildRMQ :: (Unbox a, Ord a) => Vector a -> RMQ a
readRMQ :: Unbox a => RMQ a -> Int -> a
queryMin :: (Unbox a, Ord a) => RMQ a -> Int -> Int -> a
newtype SparseTable (f :: Type -> Type) a = SparseTable {
- getSparseTable :: Vector (Vector a)
}
buildSparseTable :: forall (f :: Type -> Type) a. (Unbox a, Semigroup (f a), Coercible (f a) a) => Vector a -> SparseTable f a
readSparseTable :: Unbox a => SparseTable f a -> Int -> a
querySparseTable :: forall (f :: Type -> Type) a. (Unbox a, Semigroup (f a), Coercible (f a) a) => SparseTable f a -> Int -> Int -> a

Documentation

buildRMQ :: (Unbox a, Ord a) => Vector a -> RMQ a Source #

readRMQ :: Unbox a => RMQ a -> Int -> a Source #

queryMin :: (Unbox a, Ord a) => RMQ a -> Int -> Int -> a Source #

min a[l..r)

O(1)

Constructors

SparseTable
Fields getSparseTable :: Vector (Vector a)

Instances details

(Show a, Unbox a) => Show (SparseTable f a) Source #
Instance details Defined in Data.SparseTable Methods showsPrec :: Int -> SparseTable f a -> ShowS # show :: SparseTable f a -> String # showList :: [SparseTable f a] -> ShowS #
(Unbox a, Eq a) => Eq (SparseTable f a) Source #
Instance details Defined in Data.SparseTable Methods (==) :: SparseTable f a -> SparseTable f a -> Bool # (/=) :: SparseTable f a -> SparseTable f a -> Bool #

buildSparseTable :: forall (f :: Type -> Type) a. (Unbox a, Semigroup (f a), Coercible (f a) a) => Vector a -> SparseTable f a Source #

O(1)

querySparseTable :: forall (f :: Type -> Type) a. (Unbox a, Semigroup (f a), Coercible (f a) a) => SparseTable f a -> Int -> Int -> a Source #

append[l..r)

O(1)