Safe Haskell	None
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 higher order functions applied to an entire 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

Typically, 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 in partial block access functions (foldPart or actPart).

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 a target block index.
-> (Int -> Int -> Int -> m ())	Function: `actPart` function that takes a target block index and a half-open interval in it.
-> Int	Input: \(l\).
-> Int	Input: \(r\).
-> m ()	Unit.

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

Constraints

\(l \le r\)

Since: 1.2.5.0

foldMapM Source #

Arguments

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

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

Constraints

\(l \le r\)
The readPart function must return a valid value for an empty interval.

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 a takes target block index and returns a monoid value for it.
-> (Int -> Int -> Int -> m a)	Function: `readPart` function that a takes target block index, a half-open interval in it, and returns the output value for it.
-> Int	Input: \(l\).
-> Int	Input: \(r\).
-> m a	Concatenated output.

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

Constraints

\(l \le r\)
The readPart function must return a valid value for an empty interval.

Since: 1.2.5.0

foldM Source #

Arguments

:: Monad m
=> Int	Context: block length.
-> (a -> Int -> m a)	Function: `foldFull` function that a takes target block index and returns a monoid value for it.
-> (a -> Int -> Int -> Int -> m a)	Function: `foldPart` function that a takes target block index, a half-open interval in it and returns a monoid value for 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 a target block index and returns amonoid value for it.
-> (a -> Int -> Int -> Int -> m a)	`readPart` function that takes a target block index, a half-open interval and returns a monoid value for 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