| Safe Haskell | Safe-Inferred |
|---|---|
| Language | GHC2021 |
AtCoder.Extra.WaveletMatrix.BitVector
Description
A compact bit vector, a collection of bits that can process rank in O(1) and select in
O(logn).
Since: 1.1.0.0
Synopsis
- data BitVector = BitVector {}
- build :: Vector Bit -> BitVector
- wordSize :: Int
- csumInPlace :: PrimMonad m => MVector (PrimState m) Int -> Vector Bit -> m Int
- rank0 :: BitVector -> Int -> Int
- rank1 :: BitVector -> Int -> Int
- select0 :: BitVector -> Int -> Maybe Int
- select1 :: BitVector -> Int -> Maybe Int
- selectKthIn0 :: BitVector -> Int -> Int -> Int -> Maybe Int
- selectKthIn1 :: BitVector -> Int -> Int -> Int -> Maybe Int
Bit vector
A compact bit vector.
Since: 1.1.0.0
Constructors
| BitVector | |
Constructor
(Internal) Word-based cumultaive sum
The block size 64 for the internal cumultaive sum in the bit vector.
Since: 1.1.0.0
Arguments
| :: PrimMonad m | |
| => MVector (PrimState m) Int | Cumulative sum of length ⌈|bits|/64⌉. |
| -> 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 Source #
O(1) Counts the number of 0 bits in the interval [0,i).
Since: 1.1.0.0
rank1 :: BitVector -> Int -> Int Source #
O(1) Counts the number of 1 bits in an interval [0,i).
Since: 1.1.0.0
Select
select0 :: BitVector -> Int -> Maybe Int Source #
O(logn) 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 Source #
O(logn) Returns the index of k-th 1 (0-based), or Nothing if no such bit exists.
Since: 1.1.0.0
O(logn) Returns the index of k-th 0 (0-based) in [l,r), or Nothing if no
such bit exists.
Since: 1.1.0.0