pixie::rmq::CartesianHybridBTree< T, Compare, Index, LeafSize, UseTopSparseOverlay > Class Template Reference

Cartesian-tree value RMQ using HybridBTree-style LCA. More...

#include <cartesian_hybrid_btree.h>

Inheritance diagram for pixie::rmq::CartesianHybridBTree< T, Compare, Index, LeafSize, UseTopSparseOverlay >:

Public Types
using	Self

Public Member Functions
	CartesianHybridBTree ()=default
	Construct an empty Cartesian-tree RMQ index.
	CartesianHybridBTree (std::span< const T > values, Compare compare=Compare())
	Build a Cartesian-tree RMQ index over values.
	CartesianHybridBTree (const CartesianHybridBTree &other)
	Copy an RMQ index and rebuild internal non-owning views.
CartesianHybridBTree &	operator= (const CartesianHybridBTree &other)
	Copy-assign an RMQ index and rebuild internal non-owning views.
	CartesianHybridBTree (CartesianHybridBTree &&other) noexcept
	Move an RMQ index and rebuild internal non-owning views.
CartesianHybridBTree &	operator= (CartesianHybridBTree &&other) noexcept
	Move-assign an RMQ index and rebuild internal non-owning views.
std::size_t	size_impl () const
	Return the number of indexed values.
T	value_at_impl (std::size_t position) const
	Return the value at an indexed position.
std::size_t	arg_min_impl (std::size_t left, std::size_t right) const
	Return the first minimum position in [left, right).
std::size_t	bp_bit_count () const
	Return the number of BP bits in the Cartesian-tree RMQ encoding.
std::span< const std::uint64_t >	bp_words () const
	Return the packed BP words used by the RMQ encoding.
std::size_t	top_sparse_block_size () const
	Return the current top sparse-table block width.
std::size_t	top_sparse_block_count () const
	Return the current number of top sparse-table blocks.
std::size_t	memory_usage_bytes_impl () const
	Return owned auxiliary memory usage in bytes.
Public Member Functions inherited from pixie::rmq::RmqBase< Impl, Value >
std::size_t	size () const
	Number of indexed values.
bool	empty () const
	Whether the indexed array is empty.
std::size_t	arg_min (std::size_t left, std::size_t right) const
	Return the first minimum position in [left, right).
Value	range_min (std::size_t left, std::size_t right) const
	Return the minimum value in [left, right).
std::size_t	memory_usage_bytes () const
	Return owned auxiliary memory usage in bytes when implemented.

Static Public Member Functions
static std::size_t	top_sparse_block_size_for (std::size_t value_count)
	Return the top sparse-table block width chosen for a value count.
static std::size_t	top_sparse_block_count_for (std::size_t value_count)
	Return the number of top sparse-table blocks for a value count.

Static Public Attributes
static constexpr std::size_t	npos = RmqBase<Self, T>::npos
static constexpr Index	invalid_index = std::numeric_limits<Index>::max()
static constexpr std::size_t	kMinTopSparseBlockSize = 4096
static constexpr std::size_t	kMaxTopSparseBlocks = std::size_t{1} << 14
static constexpr bool	kUseTopSparseOverlay = UseTopSparseOverlay
Static Public Attributes inherited from pixie::rmq::RmqBase< Impl, Value >
static constexpr std::size_t	npos = std::numeric_limits<std::size_t>::max()
	Sentinel returned when no valid query answer exists.

Detailed Description

template<class T, class Compare = std::less<T>, class Index = std::size_t, std::size_t LeafSize = 512, bool UseTopSparseOverlay = true>
class pixie::rmq::CartesianHybridBTree< T, Compare, Index, LeafSize, UseTopSparseOverlay >

Cartesian-tree value RMQ using HybridBTree-style LCA.

This class follows the same public value-RMQ specification as the other value RMQ backends. It builds a stable Ferrada-Navarro BP Cartesian-tree encoding, uses RankSelectSupport<> for close-parenthesis rank/select, and delegates the BP-depth minimum query to detail::HybridBTreePlusMinusOne. The BP-depth backend keeps a configurable low-level leaf size, fixed 192-entry middle nodes with embedded minima, and fixed 256-entry high nodes. A single coarse value-level sparse table is checked first; it uses at least 4096-value blocks and grows the block width when needed so the top layer has at most 2^14 blocks. Wide queries whose padded block-cover minimum lies inside the requested range return from this top table without touching the global BP rank/select path. BP construction uses a succinct monotone bit-stack, preserving the same stable Cartesian-tree shape without an n-entry index stack.

This implementation is included from pixie/rmq.h as the compact Cartesian-tree reduction backed by a HybridBTree-shaped ±1 RMQ index.

Member Typedef Documentation

Self

template<class T, class Compare = std::less<T>, class Index = std::size_t, std::size_t LeafSize = 512, bool UseTopSparseOverlay = true>

using pixie::rmq::CartesianHybridBTree< T, Compare, Index, LeafSize, UseTopSparseOverlay >::Self

Initial value:

 
      CartesianHybridBTree<T, Compare, Index, LeafSize, UseTopSparseOverlay>

Constructor & Destructor Documentation

CartesianHybridBTree()

template<class T, class Compare = std::less<T>, class Index = std::size_t, std::size_t LeafSize = 512, bool UseTopSparseOverlay = true>

pixie::rmq::CartesianHybridBTree< T, Compare, Index, LeafSize, UseTopSparseOverlay >::CartesianHybridBTree ( std::span< const T > values, Compare compare = Compare() )

inlineexplicit

Build a Cartesian-tree RMQ index over values.

The values are not copied and must outlive this object. Equal values stay stable: the smaller index remains the first minimum.

Member Function Documentation

memory_usage_bytes_impl()

template<class T, class Compare = std::less<T>, class Index = std::size_t, std::size_t LeafSize = 512, bool UseTopSparseOverlay = true>

std::size_t pixie::rmq::CartesianHybridBTree< T, Compare, Index, LeafSize, UseTopSparseOverlay >::memory_usage_bytes_impl ( ) const

inline

Return owned auxiliary memory usage in bytes.

Counts this value-RMQ object, packed Cartesian BP words, the top sparse overlay, and nested BP rank/select and ±1 RMQ indexes. The external input values are not owned and are excluded.

---

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

• include/pixie/rmq/cartesian_hybrid_btree.h