Algos
Algos is a collection of different algorithms, mainly used for programming competitions (like ACM ICPC).
Contains algorithms divided by topic. Most algorithms are runnable from the file as is. All algorithms have a reference problem on which they can be tested (or are waiting for this problem to be provided).
Feel free to use for any purposes (you may contact authors before, if need be).
You may also see the original repository of Algos. Feel free to contribute.
For any suggestions, corrections or questions contact adilet@adilet.org
Table of content:
Cartesian Tree
Reference problem: #2782

Complexity: O(logN) per operation.


Cartesian tree is a randomized balanced binary search tree. 
Cartesian Tree with implicit keys
Reference problem: #111240

Complexity: O(logN) per operation.


Cartesian tree with implicit keys is a powerful modification of cartesian tree, which can be used to solve many interesting problems. This implementation solves the problem of finding range minimum and also can perform reverse of an array segment. 
Fenwick tree
Reference problem: #3317

Complexity: O(logN) per operation.


Fenwick tree is a simple and easytowrite data structure which can be used to find the value of some reversible function on the interval and also change the value of some element. This implementation can find the sum on the interval and update any arbitrary element. 
Fenwick tree 2D
Reference problem: #3013

Complexity: O(log^{2}N) on query.


Extension of Fenwick tree on 2D case. This code can find the sum on the rectangle and update any arbitrary element. 
Implicit segment tree
Reference problem: #3327

Complexity: O(logN) per query.
Memory: O(QlogN). Q — number of queries, N — interval length 

Implicit segment tree is a modification of segment tree which creates nodes only when they are needed. It can be used on big intervals like [1..10^{9}]. This code performs addition on the interval and getting the value of some element. 
Queue with minimum
Reference problem: #756

Complexity: O(1) on operation.


Modification of queue, which allows finding the minimum element in it. 
Segment Tree (AssignSum)
Reference problem: Problem C from here

Complexity: O(logN) per operation.


Segment tree is a powerful data structure which can perform many operations on the intervals in O(logN) time. This implementation performs assignment and gets the sum on the interval. 
Segment Tree (minimum on a segment and update)
Reference problem: #3309

Complexity: O(logN) per operation.


Segment tree. Solves RMQ problem (maximum on a segment and value update). 
Sparse table
Reference problem: #3309

Complexity: O(NlogN) on precalculation, O(1) on query.


Solves static RMQ problem (range minimum/maximum query without element changes). 
Convex Hull trick
Reference problem: CFR#189, task C

Complexity: O(N).


Convex Hull trick is a geometry based dynamic programming modification. More about it 
Longest Increasing Sequence
Reference problem: #1794

Complexity: O(NlogN).


Fast way to find longest increasing subsequence (subsequence in which each next element is greater than previous). 
Closest pair of points.
Reference problem: CLOPPAIR

Complexity: O(NlogN).


Divideandconquer approach to find the closest pair of points. 
Convex Hull
Complexity: O(NlogN).


GrahamAndrew and Graham scan methods to find convex hull (the least convex polygon containing all given points). 
BellmanFord algorithm
Reference problem: #178

Complexity: O(N * M).


BellmanFord algorithm finding shortest distances from a single vertex in graph. 
Bipartite matching
Reference problem: #1683

Complexity: O(N * M).


Kuhn algorithm for maximum matching in bipartite graph. 
Bridges search
Reference problem: Problem C from here

Complexity: O(N + M).


Algorithm for finding all bridges in the graph (edges, after removal of which graph divides into several components). 
Cutpoints search
Reference problem: Problem D from here

Complexity: O(N + M).


Algorithm for finding all cutpoints in the graph (vertices, after removal of which graph divides into several components). 
Dijkstra algorithm
Reference problem: Codeforces, 20C

Complexity: O(MlogM).


Finding minimum distances from the single source with Dijkstra algorithm. No negative edges are allowed. Best for sparse graphs. Two versions using set and heap. 
Dinic maxflow
Reference problem: #2784

Complexity: O(N * M * log(MC)), where MC is maximum edge capacity.


Dinic algorithm with scaling for finding the maximum flow. 
Eulerian path/cycle
Reference problem: #1704

Complexity: O(M).


Algorithm for finding the Eulerian path/cycle — path/cycle that visits every edge of the graph exactly once. 
FloydWarshall algorithm
Reference problem: #95

Complexity: O(N^{3}).


FloydWarshall algorithm finding shortest distance between all pairs of vertices in graph. 
FordFulkerson maxflow
Reference problem: #2783

Complexity: O(Mf), f  maxflow value.


FordFulkerson algorithm for finding the maximum flow. 
Heavylight decomposition
Reference problem: #1553

Complexity: O(N) on building,
O(log^{2}N) on query. 

Heavylight decomposition with segment trees in paths. Used for finding maximum on the path between two vertices. 
Hungarian matching
Reference problem: #394

Complexity: O(N^{3}).


Hungarian algorithm for solving the assignment problem. 
LCA. Binary ascent.
Reference problem: #111796

Complexity: O(NlogN) for preprocessing, O(logN) on query.


Finding LCA (Least common ancestor) of two vertices in the tree. Uses dp calculated on powers of 2. 
LCA. Heavylight decomposition.
Reference problem: #111796

Complexity: O(N) for preprocessing, O(logN) on query.


Finding LCA (Least common ancestor) of two vertices in the tree. Uses heavylight decomposition. 
MinCost MaxFlow Dijkstra
Reference problem: #394

Complexity: O(N^{5}) or O(N * M^{2} * logN). Less on practice.
O(N^{3}) for bipartite matching case. 

Solution to MinCost MaxFlow (or simply MinCost Flow) using Dijkstra algorithm with potentials as shortest path search method. 
MinCost MaxFlow FordBellman
Reference problem: #394

Complexity: O(N^{6}). Less on practice.
O(N^{4}) for bipartite matching case. 

Solution to MinCost MaxFlow (or simply MinCost Flow) using FordBellman algorithm as shortest path search method 
Minimum spanning tree. Kruskal algorithm
Reference problem: #1377

Complexity: O(MlogM).


Kruskal algorithm for finding the minimum spanning tree (tree connecting the given graph with minumim sum of edges). 
Minimum spanning tree. Prim algorithm
Reference problem: #185

Complexity: O(N^{2}).


Prim algorithm for finding the minimum spanning tree (tree connecting the given graph with minumim sum of edges). 
BigInt
Reference problem: not added yet.

Complexity: depends on function.


Structure implementing long arithmetic in C++. Analogous to BigInteger in Java. 
Catalan numbers
Reference problem: #140

Complexity: O(N * loglogN)


Finding Nth Catalan number modulo some mod (mod is not necessary prime). Uses Eratosthenes sieve for fast factorization 
Diophantine equation
Reference problem: #4188

Complexity: O(logX), where X — the biggest number in equation.


Solving Diophantine equations in form of a * x + b * y = c. 
Fast Fourier transformation
Reference problem: #317

Complexity: O(NlogN).


Fast Fourier transformation used to multiply long numbers. Fast nonrecursive version. 
Gauss
Reference problem: #198

Complexity: O(N^{3}).
More presicely: O(min(N, M) * N * M), where N — number of equations, M — number of variables. 

Gauss method of solving systems of linear algebraic equation. 
Number by permutation
Reference problem: #2388

Complexity: O(N^{2}).


Finding number of permutation in lexicographical order 
Permutation by number
Reference problem: #190

Complexity: O(N^{2}).


Finding permutation by its length and number in lexicographical order 
Expression result calculation
Reference problem: not added yet

Complexity: O(N)


Calculation of the value of the algebraic expression (like 2 * (5 + 7)  25 / 5). Uses recursive descend. See code for the list of supported operations. 
Merge sort
Reference problem: #766

Complexity: O(NlogN)


Merge sort for sorting the array of integers. 
Quick sort
Reference problem: #766

Complexity: O(NlogN)


Quick sort with random pivoting for sorting the array of integers. 
Radix sort
Reference problem: #766

Complexity: O(N * len), where len  maximum length of numbers.


Radix sort for sorting the array of integers. 
AhoCorasick
Reference problem: Problem K from here

Complexity: O(len of queries + sum len of initial strings)


AhoCorasick algorithm. This code finds all words in the text that contain any of the initially given words. 
Hashing
Reference problem: Problem C from here

Complexity: O(N) on precalculation, O(1) on query


Hashing in strings based problems. This code compares substrings using two hashes (one uses 2^64 as a modulo, another 10^9 + 7) 
Manacher's algorithm
Reference problem: Problem L from here

Complexity: O(N)


Manacher's algorithm for finding all subpalindromes in the string. 
Palindrome tree
Reference problem: #1750

Complexity: O(N)


Useful structure to deal with palindromes in strings. This code counts number of palindrome substrings of the string. 
Prefix function
Reference problem: #1323

Complexity: O(N)


Calculating the prefix function of the given string. 
Suffix Array
Reference problem: Problem I from here

Complexity: O(NlogN)


Building suffix array in O(NlogN). Also LCP array is calculated. This code counts number of different substrings in the string. 
Trie
Reference problem: Problem B from here

Complexity: O(total length of strings)


Builds trie (tree with characters on the edges) from the set of strings. This code counts number of different substrings in the string. 
Suffix Tree. Ukkonen's algorithm
Reference problem: Problem I from here

Complexity: O(N)


Ukkonen's algorithm for building the suffix tree. Uses sibling lists in the nodes. This code counts number of different substrings in the string. 
Z function
Reference problem: #1324

Complexity: O(N)


Calculating the Zfunction of the given string. 