cplib::StaticSizedBitTrie< T, Bits, Offset > Class Template Reference

Bit trie that manages an ordered set of integers, with compile-time fixed height. More...

#include <bit_trie.hpp>

Public Types
using	Child = StaticSizedBitTrie< T, Bits, Offset - Bits >
using	bitmap_t = uint64_t
using	size_type = std::size_t

Public Member Functions
	StaticSizedBitTrie ()
	Creates an empty trie.
size_type	size () const
	Returns the number of elements.
bool	empty () const
	Returns whether the trie is empty.
bool	insert (T val)
	Insert an elemnent. Returns whether the element is inserted (i.e. doesn't exist before insertion).
bool	erase (T val)
	Delete an elemnent. Returns whether the element is deleted (i.e. exists before deletion).
bool	find (T val) const
	Returns whether the element exists.
T	xor_min (T xor_val) const
	Returns the minimum of any element xor the give value.
std::optional< T >	next (T val) const
	Returns the smallest element no smaller than the given value, or std::nullopt if it doesn't exist.
std::optional< T >	prev (T val) const
	Returns the largest element no larger than the given value, or std::nullopt if it doesn't exist,.

Static Public Attributes
static constexpr int	branch_mask = (1 << Bits) - 1

Related Functions
(Note that these are not member functions.)
template<typename T , int U>
using	BitTrie = StaticSizedBitTrie< T, 6,(U - 1)/6 *6 >
	Convenient type alias for using StaticSizedBitTrie.

Detailed Description

template<typename T, int Bits, int Offset>
class cplib::StaticSizedBitTrie< T, Bits, Offset >

Bit trie that manages an ordered set of integers, with compile-time fixed height.

Most operations take \(O(U/B)\) time, where \(U\) is the number of bits in each element, and \(B\) is the number of bits per level in the tree. On 64-bit machines \(B=\log_2 64=6\).

The implementation mostly follows https://en.wikipedia.org/wiki/Bitwise_trie_with_bitmap.

Your code should use the type alias BitTrie instead of this class.

Template Parameters

T	The type of the elements. Should be an unsigned integer type.
Bits	Number of bits to look at per level.
Offset	The starting position of bits to look at for the current level.

Member Function Documentation

xor_min()

template<typename T , int Bits, int Offset>

T cplib::StaticSizedBitTrie< T, Bits, Offset >::xor_min ( T  xor_val ) const

inline

Returns the minimum of any element xor the give value.

In other words, this returns \(\min_{a\in S}{a \oplus x}\), the minimum value after xor. To get the element that minimizes the xor value ( \(\mathrm{argmin}\) instead of \(\min\)), simply xor the returned value with the argument, since \(a \oplus x \oplus x=a\)

Friends And Related Function Documentation

BitTrie

template<typename T , int Bits, int Offset>

template<typename T , int U>

using BitTrie = StaticSizedBitTrie<T, 6, (U - 1) / 6 * 6>

related

Convenient type alias for using StaticSizedBitTrie.

Template Parameters

T	The type of the elements. Should be an unsigned integer type.
U	Number of bits in each element. That is, all elements are integers in the range of \([0,2^U-1]\).

---

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

• src/cplib/order/bit_trie.hpp