cplib::WaveletArray< T, M > Class Template Reference

Efficient representation of a wavelet tree, supporting various static range queries. More...

#include <wavelet_array.hpp>

Public Types
using	size_type = BitDict::size_type

Public Member Functions
	WaveletArray ()
	Creates an empty WaveletArray.
	WaveletArray (std::vector< T > &&data)
	Creates a WaveletArray by consuming an array of elements.
size_type	size () const
	Returns the number of elements.
T	get (size_type idx) const
	Returns the element at the given index.
T	range_nth (size_type left, size_type right, size_type n) const
	Returns the 0-indexed n-th smallest element in the range [left, right).
size_type	range_count (size_type left, size_type right, T val) const
	Returns the number of the given value in the range [left, right).
size_type	range_count_between (size_type left, size_type right, T low, T high) const
	Returns the number of elements in the range [left, right) whose values are between [low, high].

Static Public Member Functions
static WaveletArray	build_and_sort (T *data, size_type size)
	Builds a WaveletArray from a mutable buffer, sorting it in place as a side effect.

Static Public Attributes
static constexpr T	max_value = M == std::numeric_limits<T>::digits ? std::numeric_limits<T>::max() : (T(1) << M) - 1

Detailed Description

template<typename T, int M = std::numeric_limits<T>::digits>
class cplib::WaveletArray< T, M >

Efficient representation of a wavelet tree, supporting various static range queries.

Each level of the wavelet tree is stored as a BitDict.

Template Parameters

T	Type of elements. Must be an unsigned integer type.
M	Specify that all elements are integers in \([0,2^M-1]\). It is propotional to the complexity of most operations and should be set as small as possible.

Member Function Documentation

build_and_sort()

template<typename T , int M = std::numeric_limits<T>::digits>

static WaveletArray cplib::WaveletArray< T, M >::build_and_sort ( T *  data, size_type  size  )

inlinestatic

Builds a WaveletArray from a mutable buffer, sorting it in place as a side effect.

The side effect is rarely desirable and the original data is usually discarded afterwards. Runs in \(O(NM)\) time.

get()

template<typename T , int M = std::numeric_limits<T>::digits>

T cplib::WaveletArray< T, M >::get ( size_type  idx ) const

inline

Returns the element at the given index.

Requires 0 <= idx < size(). Calls \(O(M)\) BitDict operations.

range_count()

template<typename T , int M = std::numeric_limits<T>::digits>

size_type cplib::WaveletArray< T, M >::range_count ( size_type  left, size_type  right, T  val  ) const

inline

Returns the number of the given value in the range [left, right).

Requires 0 <= left < right <= size() and 0 <= value <= max_value. Calls \(O(M)\) BitDict operations.

range_count_between()

template<typename T , int M = std::numeric_limits<T>::digits>

size_type cplib::WaveletArray< T, M >::range_count_between ( size_type  left, size_type  right, T  low, T  high  ) const

inline

Returns the number of elements in the range [left, right) whose values are between [low, high].

Requires 0 <= left < right <= size() and 0 <= low <= high <= max_value. Note that the value range is inclusive, to allow using the maximum value of the type T. Calls \(O(M)\) BitDict operations.

range_nth()

template<typename T , int M = std::numeric_limits<T>::digits>

T cplib::WaveletArray< T, M >::range_nth ( size_type  left, size_type  right, size_type  n  ) const

inline

Returns the 0-indexed n-th smallest element in the range [left, right).

Requires 0 <= left < right <= size() and 0 <= n < right - left. Calls \(O(M)\) BitDict operations.

---

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

• src/cplib/range/wavelet_array.hpp