AtCoder.Extra.WaveletMatrix

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

Wavelet Matrix

data WaveletMatrix

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

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

Since: 1.1.0.0

Access (indexing)

access :: WaveletMatrix -> Int -> Maybe Int

\(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

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

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

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

\(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

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

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

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

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

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

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

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

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

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

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

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)]

\(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)]

\(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