AtCoder.Extra.WaveletMatrix.BitVector

A compact bit vector, a collection of bits that can process rank in \(O(1)\) and select in \(O(\log n)\).

Since: 1.1.0.0

Bit vector

data BitVector

A compact bit vector.

Since: 1.1.0.0

Constructors

BitVector

Fields

• bitsBv :: !(Vector Bit)

  Packed bits.

  Since: 1.1.0.0

• csumBv :: !(Vector Int)

  Cumulative sum of bits by 64 words.

  Since: 1.1.0.0

Instances

Show BitVector

Defined in AtCoder.Extra.WaveletMatrix.BitVector

Methods

showsPrec :: Int -> BitVector -> ShowS

show :: BitVector -> String

showList :: [BitVector] -> ShowS

Eq BitVector

Defined in AtCoder.Extra.WaveletMatrix.BitVector

Methods

(==) :: BitVector -> BitVector -> Bool

(/=) :: BitVector -> BitVector -> Bool

Constructor

build :: Vector Bit -> BitVector

\(O(n)\) Creates a BitVector.

Since: 1.1.0.0

(Internal) Word-based cumultaive sum

wordSize :: Int

The block size \(64\) for the internal cumultaive sum in the bit vector.

Since: 1.1.0.0

csumInPlace

Arguments

:: PrimMonad m

=> MVector (PrimState m) Int

Cumulative sum of length \(\lceil |\mathrm{bits}| / 64 \rceil\).

-> Vector Bit

Bits

-> m Int

Sum of the bits

\(O(n)\) Calculates the cumulative sum in-place for the bit vector and returns the sum.

Since: 1.1.0.0

Rank

rank0 :: BitVector -> Int -> Int

\(O(1)\) Counts the number of \(0\) bits in the interval \([0, i)\).

Since: 1.1.0.0

rank1 :: BitVector -> Int -> Int

\(O(1)\) Counts the number of \(1\) bits in an interval \([0, i)\).

Since: 1.1.0.0

Select

select0 :: BitVector -> Int -> Maybe Int

\(O(\log n)\) Returns the index of \(k\)-th \(0\) (0-based), or Nothing if no such bit exists.

Since: 1.1.0.0

select1 :: BitVector -> Int -> Maybe Int

\(O(\log n)\) Returns the index of \(k\)-th \(1\) (0-based), or Nothing if no such bit exists.

Since: 1.1.0.0

selectKthIn0

Arguments

:: BitVector

A bit vector

-> Int

\(l\)

-> Int

\(r\)

-> Int

\(k\)

-> Maybe Int

The index of \(k\)-th \(0\) in \([l, r)\)

\(O(\log n)\) Returns the index of \(k\)-th \(0\) (0-based) in \([l, r)\), or Nothing if no such bit exists.

Since: 1.1.0.0

selectKthIn1

Arguments

:: BitVector

A bit vector

-> Int

\(l\)

-> Int

\(r\)

-> Int

\(k\)

-> Maybe Int

The index of \(k\)-th \(1\) in \([l, r)\)

\(O(\log n)\) Returns the index of \(k\)-th \(1\) (0-based) in \([l, r)\), or Nothing if no such bit exists.

Since: 1.1.0.0