Safe Haskell	Safe-Inferred
Language	GHC2021

AtCoder.Extra.WaveletMatrix

Contents

Wavelet Matrix
Constructors
Access (indexing)
Rank (count)
Selection
Quantile (value-ordered access)
Lookup
Conversions

Description

A static Wavelet Matrix.

Notation

Let $S$ be the set of values in your wavelet matrix. We use $|S|$ to denote the number of distinct values contained within this set $(|S| \lt n)$ .

Since: 1.1.0.0

Synopsis

data WaveletMatrix = WaveletMatrix {
- rawWM :: !RawWaveletMatrix
- xDictWM :: !(Vector Int)
}
build :: Vector Int -> WaveletMatrix
access :: WaveletMatrix -> Int -> Maybe Int
rank :: WaveletMatrix -> Int -> Int -> Int -> Int
rankBetween :: WaveletMatrix -> Int -> Int -> Int -> Int -> Int
select :: WaveletMatrix -> Int -> Maybe Int
selectKth :: WaveletMatrix -> Int -> Int -> Maybe Int
selectIn :: WaveletMatrix -> Int -> Int -> Int -> Maybe Int
selectKthIn :: WaveletMatrix -> Int -> Int -> Int -> Int -> Maybe Int
kthLargestIn :: WaveletMatrix -> Int -> Int -> Int -> Maybe Int
ikthLargestIn :: WaveletMatrix -> Int -> Int -> Int -> Maybe (Int, Int)
kthSmallestIn :: WaveletMatrix -> Int -> Int -> Int -> Maybe Int
ikthSmallestIn :: WaveletMatrix -> Int -> Int -> Int -> Maybe (Int, Int)
lookupLE :: WaveletMatrix -> Int -> Int -> Int -> Maybe Int
lookupLT :: WaveletMatrix -> Int -> Int -> Int -> Maybe Int
lookupGE :: WaveletMatrix -> Int -> Int -> Int -> Maybe Int
lookupGT :: WaveletMatrix -> Int -> Int -> Int -> Maybe Int
assocsIn :: WaveletMatrix -> Int -> Int -> [(Int, Int)]
descAssocsIn :: WaveletMatrix -> Int -> Int -> [(Int, Int)]

Wavelet Matrix

data WaveletMatrix Source #

A static Wavelet Matrix.

Since: 1.1.0.0

Constructors

WaveletMatrix
Fields rawWM :: !RawWaveletMatrix The internal wavelet matrix, where index compression is not automatically performed. Since: 1.1.0.0 xDictWM :: !(Vector Int) Index compression dictionary. Since: 1.1.0.0

Constructors

build :: Vector Int -> WaveletMatrix Source #

$O(n \log n)$ Creates a WaveletMatrix from an array $a$ .

Since: 1.1.0.0

Access (indexing)

access :: WaveletMatrix -> 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 (count)

rank Source #

Arguments

:: WaveletMatrix	A wavelet matrix
-> 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

:: WaveletMatrix	A wavelet matrix
-> 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

Selection

Example

Expand

>>> import AtCoder.Extra.WaveletMatrix qualified as WM
>>> import Data.Vector.Unboxed qualified as VU
>>> let wm = WM.build $ VU.fromList [1,1,2,1,3]
>>> WM.select wm 1
Just 0
>>> WM.selectKth wm 2 1
Just 3
>>> WM.selectIn wm {- [l, r) -} 1 4 {- x -} 1
Just 1
>>> WM.selectKthIn wm {- [l, r) -} 1 4 {- k -} 1 {- x -} 1
Just 3

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

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

Since: 1.1.0.0

selectKth Source #

Arguments

:: WaveletMatrix	A wavelet matrix
-> 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

:: WaveletMatrix	A wavelet matrix
-> Int	$l$
-> Int	$r$
-> Int	$y$
-> 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

:: WaveletMatrix	A wavelet matrix
-> 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)

kthLargestIn Source #

Arguments

:: WaveletMatrix	A wavelet matrix
-> Int	$l$
-> Int	$r$
-> Int	$k$
-> Maybe Int	$k$ -th largest $y$ in $[l, r)$

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

Since: 1.1.0.0

ikthLargestIn Source #

Arguments

:: WaveletMatrix	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 the interval $[l, r)$ , returns both the index and the value of the $k$ -th (0-based) largest value. Note that duplicated values are treated as distinct occurrences.

Since: 1.1.0.0

kthSmallestIn Source #

Arguments

:: WaveletMatrix	A wavelet matrix
-> Int	$l$
-> Int	$r$
-> Int	$k$
-> Maybe Int	$k$ -th largest $y$ in $[l, r)$

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

Since: 1.1.0.0

ikthSmallestIn Source #

Arguments

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

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

Since: 1.1.0.0

Lookup

lookupLE Source #

Arguments

:: WaveletMatrix	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

:: WaveletMatrix	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

lookupGE Source #

Arguments

:: WaveletMatrix	A wavelet matrix
-> 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

:: WaveletMatrix	A wavelet matrix
-> 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 :: WaveletMatrix -> 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

descAssocsIn :: WaveletMatrix -> 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

Key	Shortcut
s	Open this search box
esc	Close this search box
↓,ctrl + j	Move down in search results
↑,ctrl + k	Move up in search results
↵	Go to active search result