Safe Haskell	None
Language	Haskell2010

SparseTable

Description

Sparse table

Structure for fast static range fold queries. Useful when the elements do not form a group, otherwise prefix sums can be used.

Sources:

Let n = r - l + 1 in all instances below.

Synopsis

fromListSP :: Semigroup e => (Int, Int) -> [e] -> Int -> Int -> e
fromListISP :: Idempotent e => (Int, Int) -> [e] -> Int -> Int -> e
fromListUSP :: (IArray UArray e, forall s. MArray (STUArray s) e (ST s)) => (e -> e -> e) -> (Int, Int) -> [e] -> Int -> Int -> e
fromListIUSP :: (IArray UArray e, forall s. MArray (STUArray s) e (ST s)) => (e -> e -> e) -> (Int, Int) -> [e] -> Int -> Int -> e
buildSP :: MArray a e (ST s) => (e -> e -> e) -> (Int, Int) -> [e] -> ST s (a (Int, Int) e)
foldSP :: IArray a e => (e -> e -> e) -> a (Int, Int) e -> Int -> Int -> e
foldISP :: IArray a e => (e -> e -> e) -> a (Int, Int) e -> Int -> Int -> e

Documentation

fromListSP :: Semigroup e => (Int, Int) -> [e] -> Int -> Int -> e Source #

Constructs a range fold function from a list. O(n log n) to construct the structure and O(log n) for each query.

fromListISP :: Idempotent e => (Int, Int) -> [e] -> Int -> Int -> e Source #

Constructs a range fold function from a list, when the semigroup is idempotent. O(n log n) to construct the structure and O(1) for each query.

fromListUSP :: (IArray UArray e, forall s. MArray (STUArray s) e (ST s)) => (e -> e -> e) -> (Int, Int) -> [e] -> Int -> Int -> e Source #

Constructs a range fold function from a list. Uses an unboxed array. O(n log n) to construct the structure and O(log n) for each query.

fromListIUSP :: (IArray UArray e, forall s. MArray (STUArray s) e (ST s)) => (e -> e -> e) -> (Int, Int) -> [e] -> Int -> Int -> e Source #

Constructs a range fold function from a list, when the semigroup is idempotent. Uses an unboxed array. O(n log n) to construct the structure and O(1) for each query.

buildSP :: MArray a e (ST s) => (e -> e -> e) -> (Int, Int) -> [e] -> ST s (a (Int, Int) e) Source #

Builds a sparse table. O(n log n). Prefer the fromList functions.

foldSP :: IArray a e => (e -> e -> e) -> a (Int, Int) e -> Int -> Int -> e Source #

Folds a range on a sparse table. O(log n). Prefer the fromList functions.

foldISP :: IArray a e => (e -> e -> e) -> a (Int, Int) e -> Int -> Int -> e Source #

Folds a range on a sparse table, when the semigroup is idempotent. O(1). Prefer the fromList functions.