Algorithms

Links

• Math Notes
• Graph Notes

Library Files

convolution

• convolution/and.hpp
• convolution/or.hpp

data_structures

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

dp

• Rerooting (dp/rerooting.hpp)

graph

• Articulation Points (graph/articulation_points.hpp)
• graph/auxiliary_tree.hpp
• graph/bellman_ford.hpp
• graph/bipartite_coloring.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
• Euler's totient function (math/euler_phi.hpp)
• Extended Euclidean Algorithm (math/extgcd.hpp)
• Factor (math/factor.hpp)
• math/floor_div.hpp
• math/linear_sieve.hpp
• Möbius function (math/mobius.hpp)
• math/p_recursive.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

optimization

• A Polynomial-time Algorithm for the Change-Making Problem (optimization/canonical_coin_system.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
• segment_tree/sparse_lazy_segtree.hpp
• segment_tree/sparse_segtree.hpp
• segment_tree/sparse_segtree_2d.hpp

sparse_table

• Sparse Table (sparse_table/sparse_table.hpp)

splay

• splay/splay_set.hpp

transform

• transform/subset_mobius.hpp
• transform/subset_zeta.hpp
• transform/superset_mobius.hpp
• transform/superset_zeta.hpp

treap

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

tree

• Cartesian Tree (tree/cartesian_tree.hpp)
• tree/tree_diameter.hpp

wavelet

• wavelet/wavelet_matrix.hpp

Verification Files

test/convolution

• test/convolution/bitwise_and_convolution.test.cpp
• test/convolution/bitwise_or_convolution.test.cpp

test/data_structures

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

test/dp

• test/dp/rerooting.test.cpp

test/graph

• test/graph/aoj1404.test.cpp
• test/graph/articulation_points.test.cpp
• test/graph/bellman_ford.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/aizu0009.test.cpp
• test/math/aizu2870.test.cpp
• test/math/aizu3614.test.cpp
• test/math/binomial_coefficient_prime_mod.test.cpp
• test/math/euler_phi.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/math/yuki106.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/optimization

• test/optimization/aizu2069.test.cpp
• test/optimization/aizu2963.test.cpp

test/segment_tree

• test/segment_tree/aizu1625.test.cpp
• test/segment_tree/segtree_2d.test.cpp
• test/segment_tree/segtree_beats.test.cpp
• test/segment_tree/sparse_lazy_segtree.test.cpp
• test/segment_tree/sparse_segtree.test.cpp
• test/segment_tree/sparse_segtree_2d.test.cpp

test/sparse_table

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

test/transform

• test/transform/chayas.test.cpp

test/treap

• test/treap/treap_set.test.cpp

test/tree

• test/tree/cartesian_tree.test.cpp
• test/tree/tree_diameter.test.cpp

test/wavelet

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