pixie::rmq Namespace Reference

Namespaces
namespace	utils

Classes
class	CartesianHybridBTree
	Cartesian-tree value RMQ using HybridBTree-style LCA. More...
class	CartesianRmM
	Ferrada-Navarro Cartesian-tree RMQ using rmM support. More...
class	HybridBTree
	Hybrid B-tree RMQ with compact per-level selectors. More...
class	RmqBase
	CRTP facade for static range-minimum-query indexes. More...
class	SdslSct
	Optional value-RMQ adapter over sdsl::rmq_succinct_sct. More...
class	SegmentTree
	Static iterative segment-tree RMQ baseline. More...
class	SparseTable
	Static sparse-table RMQ baseline. More...

Typedefs
template<class T, class Compare = std::less<T>, class Index = std::size_t, std::size_t LeafSize = 512>
using	CartesianBTree = CartesianHybridBTree<T, Compare, Index, LeafSize, false>
	Cartesian-tree RMQ variant without the value-level top sparse overlay.

Enumerations
enum class	HybridBTreeLeafSelector { PrefixSuffix , BP }
	Low-level selector implementation used by HybridBTree leaves.

Detailed Description

rmM-backed Cartesian RMQ.

The benchmark harness registers this retained variant as rmq_cartesian_rmm and rmq_build_cartesian_rmm. It is included from pixie/rmq.h with the rest of the retained RMQ backends.

Diagnostic snapshot, 2026-06-13:

Focused value-RMQ rows, N=2^22 values, CPU mean across 5 repetitions. Command shape: taskset -c 0 ./build/benchmark-all-backends/rmq_benchmarks –benchmark_filter='^rmq_(cartesian_rmm|sdsl_sct)/4194304/'

max width	CartesianRmM (ns)	SdslSct (ns)
64	121.0	211.0
4096	310.0	757.0
2^18	529.0	1057.0
2^22	598.0	979.0

Raw BP rmM rows at 2^23 bits, Q=32768, CPU mean across 5 repetitions. Command shape: ./build/benchmark-all-backends/rmm_{btree,sdsl}_benchmarks –ops=range_min_query_pos,range_min_query_val –explicit_sizes=8388608 –Q=32768

backend	range_min_pos (ns)	range_min_val (ns)
RmMBTree	602.0	540.0
SdslRmMTree	727.0	742.0

The 2026-06-13 optimization pass streams cover nodes instead of materializing a zero-initialized per-query cover, adds a combined min position/value query for the Cartesian adapter, and uses a minimum-only boundary scanner for range-min position/value queries. Current perf samples for raw range_min_query_pos are concentrated in for_each_cover_node(), scan_min_range(), and summary_at().

Historical build snapshot after select0-only BP rank/select construction, 2026-06-13, before the RmMBTree full-block summary fast path. Command shape: taskset -c 0 ./build/benchmark-all-backends/rmq_benchmarks –benchmark_filter='^rmq_build_(cartesian_rmm|cartesian_hybrid_btree|sdsl_sct)/(4194304|67108864)$' –benchmark_repetitions=5

CPU mean, milliseconds.

N	CartesianRmM	CartesianHybridBTree	SdslSct
2^22	54.407	49.361	41.317
2^26	915.712	795.562	666.048

Historical construction perf profile snapshot, 2026-06-13, before the RmMBTree full-block summary fast path. Profiling build: RelWithDebInfo, -O3, debug info, frame pointers. Rows are N=2^26 build benchmarks sampled with perf at 999 Hz.

CartesianHybridBTree: 867 ms CPU in the profiled run. BP construction is the dominant cost: the succinct monotone-stack operations plus BP writes account for roughly two thirds of samples. Top sparse-table construction is about 6%. CartesianRmM: 1013 ms CPU in the profiled run. BP construction was still the dominant cost, while rmM summary construction added a visible second cost: summarize_bits()/bit() lines accounted for about 14%. Benchmark dataset generation was about 5% in both rows.

Typedef Documentation

CartesianBTree

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

using pixie::rmq::CartesianBTree = CartesianHybridBTree<T, Compare, Index, LeafSize, false>

Cartesian-tree RMQ variant without the value-level top sparse overlay.

This alias keeps the same Cartesian BP encoding and BP-depth B-tree backend as CartesianHybridBTree, but every query goes directly through the Cartesian-tree reduction. It is useful as a stable benchmark reference for measuring the value-level top sparse table separately.