Algorithm Library for C++

Notes

• This library is written for competitive programming.
• It's made to be copied and pasted to subbmissions during a contest, so there is no header files.
• Competitive programming is, so to speak, a coding race, so I use using namespace std in each file.
  • I know this is an evil thing to do, but I need to do this in order to code faster.

DataStructures

• binary_indexed_tree.cpp : Binary Indexed Tree(BIT), also known as Fenwick Tree. It achives O(logN) time complexity for Range Sum Query.

• coordinate_compression.cpp : Coordinate Compression, a commonly used technique which is to map larger values to smaller distinct values.

• doubling.cpp : Doubling, also a commonly used technique similar to pointer jumping.

• segment_tree.cpp : Segment Tree, also used for Range Sum Query. There is no lazy version yet, but I'm working on it.

• suffix_array.cpp : Constructs a Suffix Array with O(n) complexity by using the SA-IS algorithm.

• union_find_tree.cpp : Union Find Tree, also known as disjoint-set data structure

Geometry

• geometry2d.cpp : 2D geometry library used for plane figure problems.

Graph

• ford_fulkerson.cpp : Ford-Fulkerson algorithm

• graph.cpp : Trying to make a comprehensive graph class which has all the graph algorithms I've implemented, but I'm still working on it.

• kruscal.cpp : Krucsal's algorithm

• dijkstra.cpp : Dijkstra's algorithm

• bellman_ford.cpp : Bellman-Ford algorithm

• warshall_floyd.cpp : Warshall-Floyd algorithm

• topological_sort.cpp : Topological sorting for DAGs.

Math

• matrix.cpp 2d matrix class. Not finished yet.

• modlong.cpp : modlong is a integer type that applies % MOD after every opperation( such as + - * / pow comb fact).

• prime_factorization.cpp : Prime Factorization

• utils.cpp : Math utility functions such as gcd and lcm.