Safe Haskell	Safe-Inferred
Language	GHC2021

AtCoder.Extra.SqrtDecomposition

Description

Square root decomposition is a technique that divides a sequence of values into around \(\sqrt n\) blocks, aggregating the state information for each block. It allows user to process interval query block by block, typically in \(O(\sqrt n)\) time, where a whole block processing take \(O(1)\) time and partial block processing take \(O(\sqrt n)\) time.

For simplicity, in this document, we assume that highder order functions applided to an entier block (readFull and actFull) work in \(O(1)\) time, and those applied to a part of block work in \(O(\sqrt n)\) time. In total, \(q\) query processing takes \(O(q \sqrt n)\) time. Note that it's a rather large number and often requires performance tuning.

Lazy propagation

Typiaclly, an action to a whole block can be delayed; store the aggregation value for the block, delay the internal sequence update, and restore them when part of the block is accessed. Such lazy propagation should be handled on the user side on partial block access functions (foldPart or actPart) are called.

Since: 1.2.5.0

Synopsis

forM_ :: Monad m => Int -> (Int -> m ()) -> (Int -> Int -> Int -> m ()) -> Int -> Int -> m ()
foldMapM :: (Monad m, Semigroup a) => Int -> (Int -> m a) -> (Int -> Int -> Int -> m a) -> Int -> Int -> m a
foldMapWithM :: Monad m => Int -> (a -> a -> a) -> (Int -> m a) -> (Int -> Int -> Int -> m a) -> Int -> Int -> m a
foldM :: Monad m => Int -> (a -> Int -> m a) -> (a -> Int -> Int -> Int -> m a) -> a -> Int -> Int -> m a
foldM_ :: Monad m => Int -> (a -> Int -> m a) -> (a -> Int -> Int -> Int -> m a) -> a -> Int -> Int -> m ()

Documentation

These function signatures try to resemble those for lists.

forM_ Source #

Arguments

:: Monad m
=> Int	Context: block length.
-> (Int -> m ())	Function: `actFull` function that takes target block index.
-> (Int -> Int -> Int -> m ())	Function: `actPart` function that takes target block index, left index and right index.
-> Int	Input: \(l\).
-> Int	Input: \(r\).
-> m ()	Unit.

\(O(\sqrt n)\) Runs user function for each block.

foldMapM Source #

Arguments

:: (Monad m, Semigroup a)
=> Int	Context: block length.
-> (Int -> m a)	Function: `readFull` function that takes target block index and returns monoid value of it.
-> (Int -> Int -> Int -> m a)	Function: `readPart` function that takes target block index, left index and right index, and returns monoid value for it.
-> Int	Input: \(l\).
-> Int	Input: \(r\).
-> m a	Concatenated output.

\(O(\sqrt n)\) Runs user function for each block and concatanate their monoid output.

Constraints

\(l \le r\)
If an empty interval is queried, the readPart function must return a valid value.

Since: 1.2.5.0

foldMapWithM Source #

Arguments

:: Monad m
=> Int	Context: block length.
-> (a -> a -> a)	Merges function for output values.
-> (Int -> m a)	Function: `readFull` function that takes target block index and returns monoid value of it.
-> (Int -> Int -> Int -> m a)	Function: `readPart` function that takes target block index, left index and right index, and returns output value of it.
-> Int	Input: \(l\).
-> Int	Input: \(r\).
-> m a	Concatenated output.

\(O(\sqrt n)\) Runs user function for each block and concatanates their output with user function.

Constraints

\(l \le r\)
If an empty interval is queried, the readPart function must return a valid value.

Since: 1.2.5.0

foldM Source #

Arguments

:: Monad m
=> Int	Context: block length.
-> (a -> Int -> m a)	Function: `foldFull` function that takes target block index and returns monoid value of it.
-> (a -> Int -> Int -> Int -> m a)	Function: `foldPart` function that takes target block index, left and right local index and returns monoid value of it.
-> a	Initial folding value.
-> Int	Input: \(l\).
-> Int	Input: \(r\).
-> m a	Folding result.

\(O(\sqrt n)\) Runs user function for each block, performing left folding.

Constraints

\(l \le r\)

Since: 1.2.5.0

foldM_ Source #

Arguments

:: Monad m
=> Int	Context: Block length.
-> (a -> Int -> m a)	`readFull` function that takes target block index and returns monoid value of it.
-> (a -> Int -> Int -> Int -> m a)	`readPart` function that takes target block index, left and right local index and returns monoid value of it.
-> a	Initial folding value.
-> Int	Input: \(l\).
-> Int	Input: \(r\).
-> m ()	Unit.

\(O(\sqrt n)\) foldM with return value discarded.

Constraints

\(l \le r\)

Since: 1.2.5.0