Some data structures and algorithms that I use in competitive programming
- Segment Tree - segment_tree.cpp
- Semgent Tree with Lazy Propagation - segment_tree_lazy.cpp
- Binary Indexed / Fenwick Tree - fenwick_tree.cpp
- Sparse Table - sparse_table.cpp
- Suffix Array - suffix_array.cpp
- Build LCP Array from Suffix Array (Needs RMQ) - lcp.cpp
-
- Centroid Decomposition - centroid.cpp
- DFS for Lowest Common Ancestor with RMQ - lca_rmq.cpp
- DFS for Lowest Common Ancestor with Binary Lifting - lca_bl.cpp
- Eulerian Path / Cycle - eulerian_path.cpp
- Sieve of Eratosthenes - prime_sieve.cpp
- Fast Exponentiation - fast_power.cpp
- Matrix (for binary exponentiation) - matrix.cpp
- FFT (polynomial/large number multiplication) - fft.cpp
- Modular Inverse & Extended Euclidean Algorithm - mod_inv.cpp
- Polynomial Division - polynomial_division.cpp
- Modulo Int - mod_int.cpp
- Disjoint Set Union for numbers (O(max_value) space required) - dsu_int.cpp
- Disjoint Set Union for any type - dsu_any.cpp
- Coodinate Compression - coodinate_compression.cpp
- Custom Hash Function from neal's cf post - custom_hash.cpp
- Hashing for Pairs - pair_hash.cpp