Safe Haskell	Safe-Inferred
Language	GHC2021

AtCoder.Extra.WaveletMatrix.Raw

Contents

RawWaveletMatrix
Constructors
Access (indexing)
rank
Select
Quantile (value-ordered access)
- Safe (total)
- Unsafe
Lookup
Conversions

Description

A static Wavelet Matrix without automatic index comperssion. Consider using AtCoder.Extra.WaveletMatrix instead.

Since: 1.1.0.0

Synopsis

data RawWaveletMatrix = RawWaveletMatrix {
- heightRwm :: !Int
- lengthRwm :: !Int
- bitsRwm :: !(Vector BitVector)
- nZerosRwm :: !(Vector Int)
}
build :: HasCallStack => Int -> Vector Int -> RawWaveletMatrix
access :: RawWaveletMatrix -> Int -> Maybe Int
rankLT :: RawWaveletMatrix -> Int -> Int -> Int -> Int
rank :: RawWaveletMatrix -> Int -> Int -> Int -> Int
rankBetween :: RawWaveletMatrix -> Int -> Int -> Int -> Int -> Int
select :: RawWaveletMatrix -> Int -> Maybe Int
selectKth :: RawWaveletMatrix -> Int -> Int -> Maybe Int
selectIn :: RawWaveletMatrix -> Int -> Int -> Int -> Maybe Int
selectKthIn :: RawWaveletMatrix -> Int -> Int -> Int -> Int -> Maybe Int
kthSmallestIn :: RawWaveletMatrix -> Int -> Int -> Int -> Maybe Int
ikthSmallestIn :: RawWaveletMatrix -> Int -> Int -> Int -> Maybe (Int, Int)
kthLargestIn :: RawWaveletMatrix -> Int -> Int -> Int -> Maybe Int
ikthLargestIn :: RawWaveletMatrix -> Int -> Int -> Int -> Maybe (Int, Int)
unsafeKthSmallestIn :: RawWaveletMatrix -> Int -> Int -> Int -> Int
unsafeIKthSmallestIn :: RawWaveletMatrix -> Int -> Int -> Int -> (Int, Int)
unsafeKthLargestIn :: RawWaveletMatrix -> Int -> Int -> Int -> Int
unsafeIKthLargestIn :: RawWaveletMatrix -> Int -> Int -> Int -> (Int, Int)
lookupLE :: RawWaveletMatrix -> Int -> Int -> Int -> Maybe Int
lookupLT :: RawWaveletMatrix -> Int -> Int -> Int -> Maybe Int
lookupGE :: RawWaveletMatrix -> Int -> Int -> Int -> Maybe Int
lookupGT :: RawWaveletMatrix -> Int -> Int -> Int -> Maybe Int
assocsIn :: RawWaveletMatrix -> Int -> Int -> [(Int, Int)]
assocsWith :: RawWaveletMatrix -> Int -> Int -> (Int -> Int) -> [(Int, Int)]
descAssocsIn :: RawWaveletMatrix -> Int -> Int -> [(Int, Int)]
descAssocsInWith :: RawWaveletMatrix -> Int -> Int -> (Int -> Int) -> [(Int, Int)]

RawWaveletMatrix

data RawWaveletMatrix Source #

A static Wavelet Matrix without automatic index comperssion.

Since: 1.1.0.0

Constructors

RawWaveletMatrix
Fields heightRwm :: !Int \(\lceil \log_2 N \rceil\). Since: 1.1.0.0 lengthRwm :: !Int The length of the original array. Since: 1.1.0.0 bitsRwm :: !(Vector BitVector) The bit matrix. Each row represents (heightRwm - 1 - iRow) bit's on/off. Since: 1.1.0.0 nZerosRwm :: !(Vector Int) The number of zeros bits in each row in the bit matrix. Since: 1.1.0.0

Instances

Instances details

Show RawWaveletMatrix Source #
Instance details Defined in AtCoder.Extra.WaveletMatrix.Raw Methods showsPrec :: Int -> RawWaveletMatrix -> ShowS # show :: RawWaveletMatrix -> String # showList :: [RawWaveletMatrix] -> ShowS #
Eq RawWaveletMatrix Source #
Instance details Defined in AtCoder.Extra.WaveletMatrix.Raw Methods (==) :: RawWaveletMatrix -> RawWaveletMatrix -> Bool # (/=) :: RawWaveletMatrix -> RawWaveletMatrix -> Bool #

Constructors

build Source #

Arguments

:: HasCallStack
=> Int	The number of different values in the compressed vector.
-> Vector Int	A compressed vector
-> RawWaveletMatrix	A wavelet matrix

\(O(n \log n)\) Creates a RawWaveletMatrix from a vector \(a\).

Since: 1.1.0.0

Access (indexing)

access :: RawWaveletMatrix -> Int -> Maybe Int Source #

\(O(\log |S|)\) Returns \(a[k]\) or Nothing if the index is out of the bounds. Try to use the original array if you can.

Since: 1.1.0.0

rank

rankLT :: RawWaveletMatrix -> Int -> Int -> Int -> Int Source #

\(O(\log |S|)\) Returns the number of \(y\) in \([l, r) \times [0, y_0)\).

Since: 1.1.0.0

rank Source #

Arguments

:: RawWaveletMatrix
-> Int	\(l\)
-> Int	\(r\)
-> Int	\(y\)
-> Int	The number of \(y\) in \([l, r)\).

\(O(\log |S|)\) Returns the number of \(y\) in \([l, r)\).

Since: 1.1.0.0

rankBetween Source #

Arguments

:: RawWaveletMatrix
-> Int	\(l\)
-> Int	\(r\)
-> Int	\(y_1\)
-> Int	\(y_2\)
-> Int	The number of \(y\) in \([l, r) \times [y_1, y_2)\).

\(O(\log |S|)\) Returns the number of \(y\) in \([l, r) \times [y_1, y_2)\).

Since: 1.1.0.0

Select

select :: RawWaveletMatrix -> Int -> Maybe Int Source #

\(O(\log |S|)\) Returns the index of the first \(y\) in the sequence, or Nothing if \(y\) is not found.

Since: 1.1.0.0

selectKth Source #

Arguments

:: RawWaveletMatrix
-> Int	\(k\)
-> Int	\(y\)
-> Maybe Int	The index of \(k\)-th \(y\)

\(O(\log |S|)\) Returns the index of the \(k\)-th occurrence (0-based) of \(y\), or Nothing if no such occurrence exists.

Since: 1.1.0.0

selectIn Source #

Arguments

:: RawWaveletMatrix	A wavelet matrix
-> Int	\(l\)
-> Int	\(r\)
-> Int	\(k\)
-> Maybe Int	The index of the first \(y\) in \([l, r)\).

\(O(\log |S|)\) Given an interval \([l, r)\), it returns the index of the first occurrence (0-based) of \(y\) in the sequence, or Nothing if no such occurrence exists.

Since: 1.1.0.0

selectKthIn Source #

Arguments

:: RawWaveletMatrix
-> Int	\(l\)
-> Int	\(r\)
-> Int	\(k\)
-> Int	\(y\)
-> Maybe Int	The index of the \(k\)-th \(y\) in \([l, r)\).

\(O(\log |S|)\) Given an interval \([l, r)\), it returns the index of the \(k\)-th occurrence (0-based) of \(y\) in the sequence, or Nothing if no such occurrence exists.

Since: 1.1.0.0

Quantile (value-ordered access)

Safe (total)

kthSmallestIn Source #

Arguments

:: RawWaveletMatrix	A wavelet matrix
-> Int	\(l\)
-> Int	\(r\)
-> Int	\(k\)
-> Maybe Int	\(k\)-th largest \(y\) in \([l, r)\)

\(O(\log |S|)\) Given an interval \([l, r)\), it returns the index of the \(k\)-th (0-based) smallest value. Note that duplicated values are counted as distinct occurrences.

Since: 1.1.0.0

ikthSmallestIn Source #

Arguments

:: RawWaveletMatrix
-> Int	\(l\)
-> Int	\(r\)
-> Int	\(k\)
-> Maybe (Int, Int)	\((i, y)\) for \(k\)-th largest \(y\) in \([l, r)\)

\(O(\log |S|)\) Given an interval \([l, r)\), it returns both the index and the value of the \(k\)-th (0-based) smallest value. Note that duplicated values are counted as distinct occurrences.

Since: 1.1.0.0

kthLargestIn Source #

Arguments

:: RawWaveletMatrix	A wavelet matrix
-> Int	\(l\)
-> Int	\(r\)
-> Int	\(k\)
-> Maybe Int	\(k\)-th largest \(y\) in \([l, r)\)

\(O(\log |S|)\) Given an interval \([l, r)\), it returns the index of the \(k\)-th (0-based) largest value. Note that duplicated values are counted as distinct occurrences.

Since: 1.1.0.0

ikthLargestIn Source #

Arguments

:: RawWaveletMatrix	A wavelet matrix
-> Int	\(l\)
-> Int	\(r\)
-> Int	\(k\)
-> Maybe (Int, Int)	\((i, y)\) for \(k\)-th largest \(y\) in \([l, r)\)

\(O(\log |S|)\) Given an interval \([l, r)\), it returns both the index and the value of the \(k\)-th (0-based) largest value. Note that duplicated values are counted as distinct occurrences.

Since: 1.1.0.0

Unsafe

unsafeKthSmallestIn :: RawWaveletMatrix -> Int -> Int -> Int -> Int Source #

\(O(\log a)\)

Since: 1.1.0.0

unsafeIKthSmallestIn :: RawWaveletMatrix -> Int -> Int -> Int -> (Int, Int) Source #

\(O(\log a)\)

Since: 1.1.0.0

unsafeKthLargestIn :: RawWaveletMatrix -> Int -> Int -> Int -> Int Source #

\(O(\log a)\) Returns \(k\)-th (0-based) biggest number in \([l, r)\). Note that duplicated values are counted as distinct occurrences.

Since: 1.1.0.0

unsafeIKthLargestIn :: RawWaveletMatrix -> Int -> Int -> Int -> (Int, Int) Source #

\(O(\log a)\)

Since: 1.1.0.0

Lookup

lookupLE Source #

Arguments

:: RawWaveletMatrix	A wavelet matrix
-> Int	\(l\)
-> Int	\(r\)
-> Int	\(y_0\)
-> Maybe Int	Maximum \(y\) in \([l, r) \times (-\infty, y_0]\)

\(O(\log |S|)\) Looks up the maximum \(y\) in \([l, r) \times (-\infty, y_0]\).

Since: 1.1.0.0

lookupLT Source #

Arguments

:: RawWaveletMatrix
-> Int	\(l\)
-> Int	\(r\)
-> Int	\(x\)
-> Maybe Int	Maximum \(y\) in \([l, r) \times (-\infty, y_0)\)

\(O(\log a)\) Finds the maximum \(x\) in \([l, r)\) s.t. \(x_{0} \lt x\).

Since: 1.1.0.0

lookupGE Source #

Arguments

:: RawWaveletMatrix
-> Int	\(l\)
-> Int	\(r\)
-> Int	\(y_0\)
-> Maybe Int	Minimum \(y\) in \([l, r) \times [y_0, \infty)\).

\(O(\log |S|)\) Looks up the minimum \(y\) in \([l, r) \times [y_0, \infty)\).

Since: 1.1.0.0

lookupGT Source #

Arguments

:: RawWaveletMatrix
-> Int	\(l\)
-> Int	\(r\)
-> Int	\(y_0\)
-> Maybe Int	Minimum \(y\) in \([l, r) \times (y_0, \infty)\)

\(O(\log |S|)\) Looks up the minimum \(y\) in \([l, r) \times (y_0, \infty)\).

Since: 1.1.0.0

Conversions

assocsIn :: RawWaveletMatrix -> Int -> Int -> [(Int, Int)] Source #

\(O(\min(|S|, L) \log |S|)\) Collects \((y, \mathrm{rank}(y))\) in range \([l, r)\) in ascending order of \(y\). Note that it's only fast when the \(|S|\) is very small.

Since: 1.1.0.0

assocsWith :: RawWaveletMatrix -> Int -> Int -> (Int -> Int) -> [(Int, Int)] Source #

\(O(\log A \min(|A|, L))\) Internal implementation of assocs.

Since: 1.1.0.0

descAssocsIn :: RawWaveletMatrix -> Int -> Int -> [(Int, Int)] Source #

\(O(\min(|S|, L) \log |S|)\) Collects \((y, \mathrm{rank}(y))\) in range \([l, r)\) in descending order of \(y\). Note that it's only fast when the \(|S|\) is very small.

Since: 1.1.0.0

descAssocsInWith :: RawWaveletMatrix -> Int -> Int -> (Int -> Int) -> [(Int, Int)] Source #

\(O(\log A \min(|A|, L))\) Internal implementation of descAssoc.

Since: 1.1.0.0