cplib::BitDict Class Reference

Static bit sequence with rank query in \(O(1)\). More...

#include <bit_dict.hpp>

Public Types
using	size_type = impl::BitDictBlock::size_type

Public Member Functions
	BitDict ()
	Creates an empty BitDict.
	BitDict (size_type num_bits)
	Creates a BitDict with num_bits bits, all initialized to 0.
size_type	size () const
	Returns the number of bits.
size_type	zeros () const
	Returns the number of zero bits.
size_type	ones () const
	Returns the number of one bits.
bool	get (size_type idx) const
	Read-only access to a bit. Requires 0 <= idx < size()
void	set (size_type idx)
	Set a bit to 1. Requires 0 <= idx < size().
template<typename BitGenerator >
void	fill_with_bit_generator (BitGenerator &gen)
	Overwrite all bits with a bit generator.
void	build ()
	Set up auxiliary data to prepare for rank queries.
size_type	rank1 (size_type idx) const
	Returns the number of 1 bits in the range [0, idx).
size_type	rank0 (size_type idx) const
	Returns the number of 0 bits in the range [0, idx).
size_type	rank_to_child (size_type idx, bool bit) const
	Move one level downwards in a wavelet tree.

Detailed Description

Static bit sequence with rank query in \(O(1)\).

Together with select query, this data structure is known as Fully Indexable Dictionary. Theoretical results using \(o(N)\) space and \(O(1)\) time for both queries are known, but are of little practical interest. Practical implementations usually target large datasets on the order of \(10^8\) or more bits, where memory access is the bottleneck. In competitive programming, however, the problem size is usually no more than \(10^6\), and memory is much cheaper.

This implementation uses cache line aligned blocks to ensure that each rank query reads exactly one cache line.

Constructor & Destructor Documentation

BitDict()

cplib::BitDict::BitDict ( size_type  num_bits )

inline

Creates a BitDict with num_bits bits, all initialized to 0.

Use set() or fill_with_bit_generator() to set its content.

Member Function Documentation

fill_with_bit_generator()

template<typename BitGenerator >

void cplib::BitDict::fill_with_bit_generator ( BitGenerator &  gen )

inline

Overwrite all bits with a bit generator.

Can only be called before build(). gen will be called exactly size() times.

rank0()

size_type cplib::BitDict::rank0 ( size_type  idx ) const

inline

Returns the number of 0 bits in the range [0, idx).

Can only be called after build(). Requires 0 <= idx <= size(). Runs in \(O(1)\) time.

rank1()

size_type cplib::BitDict::rank1 ( size_type  idx ) const

inline

Returns the number of 1 bits in the range [0, idx).

Can only be called after build(). Requires 0 <= idx <= size(). Runs in \(O(1)\) time.

rank_to_child()

size_type cplib::BitDict::rank_to_child ( size_type  idx, bool  bit  ) const

inline

Move one level downwards in a wavelet tree.

Can only be called after build(). Requires 0 <= idx <= size(). Runs in \(O(1)\) time.

This method answers the following question: "If this BitDict represents a level in a wavelet tree, for a boundary located right before `idx`, where is the corresponding boundary at the 0 or 1 child in the next level?". It turns out that the answer does not depend on the structure of the wavelet tree. As a corollary, an interval [left, right) becomes [rank_to_child(left, bit), rank_to_child(right, bit)) in the next level, where bit means taking the 0-branch or the 1-branch.

set()

void cplib::BitDict::set ( size_type  idx )

inline

Set a bit to 1. Requires 0 <= idx < size().

Can only be called before build().

---

The documentation for this class was generated from the following file:

• src/cplib/range/bit_dict.hpp