Data Structure

Range-query structures and union-find variants.

Headers

Header	Summary
binary_trie.hpp	动态异或最值与第 k 小
cartesian_tree.hpp	笛卡尔树构造
cdq_dominance.hpp	多维偏序统计
common_interval_decomposition_tree.hpp	排列公共区间析合树
consecutive_segment.hpp	区间赋值与旧段枚举
disjoint_sparse_table.hpp	静态可合并信息 O(n log n)-O(1) 区间查询
double_ended_heap.hpp	双端优先队列
dynamic_bitset.hpp	动态长度位集
dynamic_range_majority.hpp	单点修改与区间出现过半的数
expression_parser.hpp	自定义运算符表达式解析
fastset.hpp	整数集合与前驱后继
fenwick_2d.hpp	二维单点加与矩形和
fractional_cascading.hpp	多组有序表联动查找
hashmap.hpp	随机哈希表
implicit_lazy_treap.hpp	动态序列区间修改与翻转
implicit_treap.hpp	动态序列分裂与合并
kd_tree.hpp	低维范围与最近邻查询
lazy_segtree.hpp	区间修改与区间合并查询
leftist_heap.hpp	可合并优先队列
link_cut_tree.hpp	动态森林路径维护
mergeable_frequency_tree.hpp	可合并频次线段树
mo.hpp	静态区间莫队
mo_with_updates.hpp	带修改莫队
persistent_affine_segtree.hpp	历史区间仿射修改与求和
persistent_dsu.hpp	可持久化并查集
persistent_order_statistics.hpp	历史版本与区间第 k 小
persistent_queue.hpp	可持久化队列
point_add_range_sum.hpp	单点加与区间和
point_add_rectangle_sum.hpp	离线点加与矩形和
point_set_range_freq.hpp	单点赋值与区间频次
potentialized_dsu.hpp	维护两点差值关系的并查集
potentialized_group_dsu.hpp	维护可逆变换关系的并查集
prefix_sum.hpp	静态前缀和
range_add_point_get.hpp	区间加与单点查询
range_linear_add_range_min.hpp	区间加一次函数与最小值
range_parallel_dsu.hpp	等长区间对应点合并
range_set_range_product.hpp	区间赋值与按顺序合并信息
rectangle_add_point_get.hpp	矩形加与单点查询
rectangle_add_rectangle_sum.hpp	矩形加与矩形和
rectangle_affine_kd_tree.hpp	矩形仿射修改与求和
rectangle_sum.hpp	静态矩形权值和
rollback_dsu.hpp	可撤销并查集
rollback_mo.hpp	只加不删的回滚莫队
segment_tree_beats.hpp	区间取 min/max、加法与求和
segtree.hpp	单点修改与区间合并查询
sliding_window_aggregation.hpp	滑动窗口内信息合并
sortable_segment_tree.hpp	区间排序与按顺序合并信息
sparse_fenwick_2d.hpp	稀疏点加与矩形和
sparse_range_affine_sum.hpp	巨大值域仿射修改与求和
sparse_segtree.hpp	巨大值域单点修改与区间查询
sparse_table.hpp	静态可重信息 O(n log n)-O(1) 区间查询
static_range_distinct.hpp	静态区间不同值计数
static_range_inversions.hpp	静态区间逆序对计数
static_range_lis_query.hpp	静态排列区间 LIS
static_range_mode.hpp	静态区间众数
static_range_xor_basis.hpp	静态区间异或线性基
tag_container.hpp	全局偏移与哈希表合并
top_k_sum.hpp	动态前 k 大元素之和
wavelet_matrix.hpp	静态区间第 k 小、频次与求和