Data Structure

Range-query structures and union-find variants.

Headers

Header	Summary
binary_trie.hpp	Multiset of fixed-width unsigned integers with xor-order queries.
cartesian_tree.hpp	Cartesian tree where each node is the minimum of its subtree. Equal values prefer the leftmost.
cdq_dominance.hpp	For each 3D point, count input points coordinate-wise no greater than it, including itself and duplicate copies, in O(n log^2 n).
common_interval_decomposition_tree.hpp	Build the strong-interval Hasse tree of a permutation. For every possible left endpoint, a lazy segment tree maintains max-min-length+1 for the suffix ending at the current position. Monotone min/max stacks update this value on exactly the ranges whose extrema change, so value zero detects a new common interval. A second stack merges adjacent value ranges into linear nodes; otherwise all nodes up to the detected boundary form one prime node. Every merge is permanent, giving a laminar tree containing exactly the strong intervals.
consecutive_segment.hpp	Interval assignment container maintaining consecutive segments of equal values.
disjoint_sparse_table.hpp	Static O(1) range product for an arbitrary associative monoid.
double_ended_heap.hpp	Priority queue supporting lazy deletion of arbitrary elements.
dynamic_bitset.hpp	Resizable packed bitset with bitwise operations, shifts, population count, and efficient iteration over set bits.
dynamic_range_majority.hpp	Point-update range-majority index. The segment tree applies Boyer--Moore cancellation to obtain the only possible majority, then a coordinate-compressed Fenwick tree for that value certifies its actual frequency. Every (position, future value) update must be supplied to the constructor so the per-value position lists can be built offline.
expression_parser.hpp	Parse identifiers, integers, parentheses, configurable binary operators, and configurable prefix unary operators into an expression tree.
fastset.hpp	Fixed-universe ordered set implemented as a hierarchy of bitsets. Level zero marks present keys and every higher level marks nonempty words below it. A predecessor or successor first scans one machine word, climbs until it finds a nonempty sibling, then descends through extreme set bits.
fenwick_2d.hpp	Dense two-dimensional Fenwick tree for point additions and rectangle sums.
fractional_cascading.hpp	Fractional cascading over sorted arrays: O(N) construction and all k lower bounds in O(log N + k) per query.
hashmap.hpp	Randomized splitmix64 hash to prevent hash collision attacks. Two xor-shift/multiply avalanche rounds spread nearby integer keys across all bits, while a process-local time-derived offset makes adversarial keys from one run useless in the next.
implicit_lazy_treap.hpp	Implicit randomized treap with reversible monoid products and lazy range actions. Each node stores both product orders, so reversing a range only swaps its children and its forward/backward aggregates. A pending action is composed at a subtree root and pushed only before structural changes, which keeps every sequence operation logarithmic in expectation.
implicit_treap.hpp	Implicit randomized treap supporting insertion, erasure, reversal, point updates, and ordered monoid products in expected O(log n) time.
kd_tree.hpp	Static two-dimensional KD-tree for rectangle reporting and nearest neighbor queries.
lazy_segtree.hpp	Lazy segment tree for a monoid acted on by a mapping monoid. Monoid provides value_type, unit(), and op(left, right). Action provides value_type, unit(), composition(newer, older), and apply(action, monoid_value).
leftist_heap.hpp	Meldable leftist heap with O(log n) push, pop, and heap merging.
link_cut_tree.hpp	Link-Cut Tree for a dynamic forest with point assignment and ordered path products; all operations take amortized O(log n) time.
mergeable_frequency_tree.hpp	Dynamic frequency segment-tree pool supporting point updates, rank queries, destructive merging, and interval extraction in O(log U).
mo.hpp	Mo's algorithm for offline half-open range queries.
mo_with_updates.hpp	Three-dimensional Mo scheduler for offline range queries mixed with point updates; callbacks own the array and aggregate state.
persistent_affine_segtree.hpp	Persistent lazy segment tree for range affine transforms and sums. Every update clones only its two boundary paths. A range copy descends in a destination version and a source version together, replacing fully covered destination nodes by the corresponding immutable source nodes. Lazy tags are pushed only into freshly cloned nodes, so every older root remains unchanged.
persistent_dsu.hpp	Fully persistent union-find. Union by size keeps every parent chain logarithmic, while a path-copying segment tree stores the parent-or-size array. Versions share all untouched segment-tree nodes, so any old version can be queried or branched from after later merges.
persistent_order_statistics.hpp	Persistent frequency segment tree for range kth and rank queries; build O(n log n), each query O(log n).
persistent_queue.hpp	Fully persistent FIFO queue using an incrementally evaluated list rotation. Each new version performs one step of reversing the rear list; the memoized stream node is shared by every branch that reaches it, so no operation has to finish an entire reversal at once.
point_add_range_sum.hpp	Sum of [l, r).
point_add_rectangle_sum.hpp	Point-add rectangle-sum data structure on sparse coordinates. All future update coordinates are registered before build(); coordinate compression inside each x-Fenwick node then supports online additions and half-open rectangle sums without allocating the full plane.
point_set_range_freq.hpp	Point assignment and exact-value frequency queries on half-open ranges, both in expected O(log n) time.
potentialized_dsu.hpp	Weighted union-find over an additive group. merge(a, b, w) enforces potential(b) - potential(a) = w.
potentialized_group_dsu.hpp	Weighted union-find over a possibly noncommutative group. Store the relative value parent(x)^-1x on every parent edge, so path compression multiplies weights from root to leaf in that order. merge(a,b,w) enforces potential(a)^-1potential(b)=w; reversing a union uses the group inverse, which preserves correctness without assuming commutativity.
prefix_sum.hpp	Static half-open range sums over an additive group. Construction stores cumulative sums with an explicit zero at position zero. The sum on [left,right) is the difference of the two boundary prefixes, so each query needs no tree traversal and preserves the value type exactly.
range_add_point_get.hpp	Add v to [l, r).
range_linear_add_range_min.hpp	Maintain an integer sequence under adding b*i+c on a range and range-minimum queries. Regard every value as a point (i, a_i). A segment tree node represents the lower convex hull of its points by the common tangent (bridge) between the two child hulls. Adding the same linear function to a whole node shears all of its points and preserves that hull, so it is stored lazily. When the children receive different additions, the bridge is restored by descending their existing bridges to the new common tangent. A minimum is found by following decreasing bridge endpoints.
range_parallel_dsu.hpp	Add all equal-offset edges between two ranges and maintain a component-pair aggregate. Level h represents intervals of length 2^h. Merging two level-h classes recursively merges their left and right halves; since each class pair succeeds only once, all downward propagation is amortized over O(n log n) interval nodes. Any length is covered by its first and last largest-power-of-two blocks.
range_set_range_product.hpp	Segment tree for assigning one value to a range and taking an ordered monoid product. For every assigned value, powers for all segment lengths are cached in a circular table. Lazy nodes refer to those cached powers, so a full-cover assignment is constant time and no idempotence or commutativity is required from the monoid.
rectangle_add_point_get.hpp	Rectangle-add point-get data structure on sparse coordinates. A half-open rectangle update is its four-corner two-dimensional difference; the value at a point is the inclusive prefix sum of those differences. Register all rectangles before build(), including rectangles added later.
rectangle_add_rectangle_sum.hpp	Dense grid supporting half-open rectangle additions and rectangle sum queries in O(log rows log columns), using four 2D Fenwick trees.
rectangle_affine_kd_tree.hpp	Offline dynamic weighted point set using a balanced two-dimensional KD-tree. Every node stores its coordinate bounding box, active-point count, weight sum, and a lazy affine tag. A rectangle operation stops at a fully covered box, while points that will be inserted later start inactive, so earlier affine updates neither count nor change them.
rectangle_sum.hpp	Offline rectangle sum. Points (x, y, weight), queries [l, r) x [d, u).
rollback_dsu.hpp	Union-find with O(log n) queries and O(1) rollback per merge.
rollback_mo.hpp	Offline half-open range scheduler for rollbackable add-only states. Each query uses add(position), snapshot(), rollback(token), and answer(id).
segment_tree_beats.hpp	Segment Tree Beats supporting range add, chmin, chmax, sum, minimum, and maximum queries; bound updates run in amortized O(log^2 n) time.
segtree.hpp	Segment tree for a monoid type. Monoid must provide using value_type, value_type unit(), and value_type op(value_type, value_type).
sliding_window_aggregation.hpp	Sliding window aggregation (SWAG) supporting push_back, pop_front, and monoid product queries.
sortable_segment_tree.hpp	Maintain a sequence of distinct integer keys and monoid values under point replacement, ordered range product, and sorting a range by key. Each maximal already-sorted block is stored as a sparse segment tree over key space, containing both forward and backward products. Sorting joins all blocks in the range; splitting a block by sequence rank restores query boundaries. A fast set tracks block starts and an outer segment tree stores one aggregate per block. Since an operation creates only O(1) boundaries, the total number of block splits and merges is linear in the operation count; periodic rebuilding bounds the persistent split-node storage.
sparse_fenwick_2d.hpp	Offline-built sparse two-dimensional Fenwick tree. Register every coordinate that may later be updated, then call build(). An x-Fenwick node stores only the registered y-coordinates contributing to it, so the dense coordinate plane is replaced by O(p log p) cells.
sparse_range_affine_sum.hpp	Dynamic lazy segment tree for an initially zero huge array. Missing nodes mean an all-zero interval; an affine tag transforms a segment sum by sum <- multiplier * sum + addition * length. Tags are composed in chronological order and queries carry inherited tags without materializing untouched children.
sparse_segtree.hpp	Sparse segment tree for an enormous mostly-identity array. Each node stores one explicitly assigned position and the monoid product of its binary-search-tree subtree; interval midpoints keep the height bounded by the coordinate bit width while requiring only one node per touched point.
sparse_table.hpp	Constant-time static range queries for associative, idempotent operations such as minimum, maximum, and gcd.
static_range_distinct.hpp	Count distinct values in every offline half-open range [l, r).
static_range_inversions.hpp	Static range inversion counter. The array is split into square-root blocks. Inversions between every contiguous block interval are precomputed, while sorted block orders and prefix frequencies account for the two partial boundary blocks of a query.
static_range_lis_query.hpp	Answer LIS lengths on subarrays of a permutation. Seaweed doubling represents semi-local LCS against the sorted permutation as a subunit-Monge permutation. Unit-Monge distance products merge the two halves, and a wavelet matrix over the resulting critical points turns each interval LIS into one orthogonal counting query.
static_range_mode.hpp	Static half-open range mode queries in O(sqrt(n) log n), with O(n sqrt(n)) preprocessing; ties return the smallest value.
static_range_xor_basis.hpp	Prefix-persistent linear bases for maximum xor and membership in a static subarray, with O(B) queries and O(nB) preprocessing.
tag_container.hpp	HashMap with a global additive tag, supporting mergeable insert and bulk offset.
top_k_sum.hpp	Dynamic multiset maintaining the sum of the k largest values in O(log n) per insert, erase, or k change.
wavelet_matrix.hpp	Coordinate-compressed static wavelet matrix with range order statistics.