My Templates for Competitive Programming ├── basic
│ ├── heap .cc
│ └── sortings .cc
├── bit_span .cc
├── bitwise .cc
├── dp
│ ├── convex_hull_optimization .cc
│ ├── longest_arithmetic_series .cc
│ ├── quadrangle_optimization .cc
│ └── single_cycle_tree .cc
├── ds
│ ├── dsu .cc # union-find set
│ ├── dsu_pst .cc # persistent union-find set, implemented by persistent segment tree
│ ├── dsu_rope .cc # persistent union-find set, implemented by rope, slower
│ ├── exact_cover .cc # X problem and dancing links
│ ├── fenwick_tree # binary indexed trees
│ │ ├── fenwick2d .cc
│ │ ├── fenwick .cc
│ │ ├── range_fenwick2d .cc
│ │ ├── range_fenwick .cc
│ │ ├── range_single_fenwick2d .cc
│ │ └── range_single_fenwick .cc
│ ├── implicit_treap .cc # treap with implicit key
│ ├── matrix .cc # multiplication and power of matrix
│ ├── persistent_array .cc
│ ├── ptreap .cc # persistent treap
│ ├── rope .cc # demo code for rope data structure
│ ├── segment_tree
│ │ ├── range_cover .cc
│ │ ├── range_pst .cc # persistent segment tree, with range modification
│ │ ├── range_st .cc
│ │ ├── single_pst .cc # persistent segment tree, single point modification
│ │ └── single_st .cc
│ ├── sparse_table .cc
│ └── treap .cc
├── flows
│ ├── max_flow .cc
│ └── min_cost_flow .cc
├── geometry .cc
├── graphs
│ ├── bcc_edge .cc # binary connected component, by edge
│ ├── bcc_vertex .cc # binary connected component, by vertex
│ ├── dominator_tree .cc # "dominator" tree of directed graph
│ ├── maximum_clique .cc # can also solve maximum-independent set
│ ├── scc .cc # strong connected component of directed graph
│ └── topo_sort .cc # topo sort of (un)directed graph
├── inverse_pair .cc # number of inverse pairs, by merge sort
├── matchings
│ └── hungary .cc # hungary matching of bipartite graph
├── math
│ ├── combine_big .cc # combination for large N by Lucas
│ ├── combine_log .cc # combination with O(N) preprocessing and O(log N) computation
│ ├── combine_small .cc # combination with O(N^2) preprocessing and O(1) computation
│ ├── crt .cc # Chinese remainder theorem solving congruence equation
│ ├── d_func .cc # calculate the number of divisors of a number by O(sqrt(N))
│ ├── euler_sieve .cc # O(N) sieve for prime numbers, euler function and lowest prime divisor
│ ├── exgcd .cc # extended gcd, and solution for ax + by = c
│ ├── fft .cc # normal fft for floating numbers
│ ├── fft_mod .cc # fft for arbitrary moduler
│ ├── inv_n .cc # moduler inverse precaculation O(N)
│ ├── josephus .cc # josephus cycle problem
│ ├── kth_fib .cc # find k-th fibonacci number by O(log N)
│ ├── lagrange .cc # lagrange sieve O(N^2)
│ ├── mu_n .cc # O(N) sieve for mu array
│ ├── newton_sqrt_root .cc # newton's method for calculation sqrt
│ ├── ntt .cc # number theory transform (moduler fft)
│ ├── number_divide .cc # the number of ways to divide a positive integer number to sum of smaller numbers
│ ├── phi_func .cc # calculate euler function by O(sqrt(N))
│ ├── phi_n .cc # precaculate euler function array by O(N)
│ ├── polynomial_inv .cc # moduler inverse of polynomial
│ ├── primality .cc # primality check, miller-robin and pollard-rho
│ ├── prime_n .cc # O(N) sieve for prime numbers
│ ├── s_func .cc # calculate sum of divisors of a number by O(sqrt(N))
│ └── young_tableaus .cc
├── partial_order .cc # divide-and-conquer solving partial order problems
├── strings
│ ├── aho_corasick .cc # aho-corasick automaton
│ ├── bkdr_hash .cc
│ ├── expression .cc # math equation evaluation
│ ├── hash_1 .cc # hashing a string with one prime moduler
│ ├── hash_2 .cc # hashing a string with two prime modulers
│ ├── manacher .cc # manacher palindrome O(N)
│ ├── p_function .cc # prefix function, kmp
│ ├── p_trie .cc # persistent trie
│ ├── sa .cc # suffix array
│ ├── suffix_automaton .cc
│ ├── trie .cc
│ ├── weight_hash .cc # hashing a multiset by weight
│ └── z_function .cc # suffix function (extended kmp)
└── trees
├── centroid .cc # centroid decomposition (divide and conquer)
└── hld .cc # heavy-light decomposition