Algorithms

Library Files

data_structures

• data_structures/ordered_set.hpp
• data_structures/potentialized_rollback_dsu.hpp
• data_structures/rollback_disjoint_set.hpp

dp

• Rerooting (dp/rerooting.hpp)

graph

• Articulation Points (graph/articulation_points.hpp)
• graph/auxiliary_tree.hpp
• Bridges (graph/bridges.hpp)
• graph/csr_graph.hpp
• graph/directed_mst.hpp
• graph/dominator_tree.hpp
• graph/dynamic_connectivity.hpp
• graph/offline_dynamic_connectivity.hpp
• graph/potentialized_offline_dynamic_connectivity.hpp

heavy_light_decomposition

• Heavy-Light Decomposition (heavy_light_decomposition/heavy_light_decomposition.hpp)

io

• io/scanner.hpp

lca

• LCA Tree (lca/lca_tree.hpp)
• lca/tarjan_offline_lca.hpp

linear_algebra

• GF(2) Matrix (linear_algebra/gf2_matrix.hpp)

link_cut_tree

• link_cut_tree/lazy_link_cut_tree.hpp
• link_cut_tree/link_cut_tree.hpp

matching

• Stable matching (matching/stable_matching.hpp)

math

• math/ceil_div.hpp
• math/combinatorics.hpp
• math/dirichlet_series.hpp
• Extended Euclidean Algorithm (math/extgcd.hpp)
• Factor (math/factor.hpp)
• math/floor_div.hpp
• Möbius function (math/mobius.hpp)
• Power tower (math/power_tower.hpp)
• Saturating (math/saturating.hpp)

mo

• mo/hilbert_mo.hpp
• mo/mo_tree.hpp
• Rollback Mo (mo/rollback_mo.hpp)
• mo/sqrt_freq_table.hpp

monoids

• monoids/affine_monoid.hpp
• monoids/reversible_monoid.hpp
• monoids/sum.hpp
• monoids/xor.hpp

random

• splitmix64 (random/splitmix64.hpp)
• xoshiro256** (random/xoshiro256starstar.hpp)

segment_tree

• 2D Segment Tree (segment_tree/segtree_2d.hpp)
• Segtree Beats (segment_tree/segtree_beats.hpp)
• segment_tree/simd_segtree.hpp

sparse_table

• Sparse Table (sparse_table/sparse_table.hpp)

splay

• splay/splay_set.hpp

treap

• treap/implicit_treap.hpp
• treap/lazy_implicit_treap.hpp
• treap/treap_set.hpp

wavelet

• wavelet/wavelet_matrix.hpp

Verification Files

test/data_structures

• test/data_structures/consistent_trading.test.cpp
• test/data_structures/ordered_set.test.cpp

test/dp

• test/dp/rerooting.test.cpp

test/graph

• test/graph/articulation_points.test.cpp
• test/graph/bridges.test.cpp
• test/graph/dijkstra.test.cpp
• test/graph/directed_mst.test.cpp
• test/graph/directed_mst_minimum_cost_arborescence.test.cpp
• test/graph/dominator_tree.test.cpp
• test/graph/dynamic_connectivity.test.cpp
• test/graph/jag_regional_2022_i.test.cpp
• test/graph/odd_trip_plans.test.cpp
• test/graph/offline_dynamic_connectivity.test.cpp
• test/graph/yuki901.test.cpp

test/heavy_light_decomposition

• test/heavy_light_decomposition/lca.test.cpp
• test/heavy_light_decomposition/vertex_add_path_sum.test.cpp
• test/heavy_light_decomposition/vertex_add_subtree_sum.test.cpp

test/io

• test/io/scanner.test.cpp

test/lca

• test/lca/lca_tree.test.cpp
• test/lca/lca_tree_jump.test.cpp
• test/lca/tarjan_offline_lca.test.cpp

test/linear_algebra

• test/linear_algebra/matrix_det_mod_2.test.cpp
• test/linear_algebra/matrix_rank_mod_2.test.cpp
• test/linear_algebra/system_of_linear_equations_mod_2.test.cpp

test/link_cut_tree

• test/link_cut_tree/dynamic_tree_vertex_set_path_composite.test.cpp
• test/link_cut_tree/lazy_link_cut_tree.test.cpp
• test/link_cut_tree/link_cut_tree.test.cpp

test/matching

• test/matching/stable_matching.stress.test.cpp

test/math

• test/math/binomial_coefficient_prime_mod.test.cpp
• test/math/extgcd.test.cpp
• test/math/factor.test.cpp
• test/math/power_tower.test.cpp
• test/math/tetration_mod.test.cpp

test/mo

• test/mo/aoj0489.test.cpp
• test/mo/aoj2270.test.cpp
• test/mo/hilbert_mo_range_kth_smallest.test.cpp
• test/mo/hilbert_mo_static_range_count_distinct.test.cpp
• test/mo/hilbert_mo_static_range_frequency.test.cpp
• test/mo/hilbert_mo_static_range_inversions_query.test.cpp
• test/mo/rollback_mo_static_range_mode_query.test.cpp

test/segment_tree

• test/segment_tree/segtree_2d.test.cpp
• test/segment_tree/segtree_beats.test.cpp

test/sparse_table

• test/sparse_table/static_range_sum.test.cpp
• test/sparse_table/static_rmq.test.cpp

test/treap

• test/treap/treap_set.test.cpp

test/wavelet

• test/wavelet/wavelet_matrix_range_kth_smallest.test.cpp
• test/wavelet/wavelet_matrix_static_range_frequency.test.cpp