Codes have mostly been written in C++. Please, consider compiling the code using C++11 or higher to avoid any compilation issues or warnings.
The list of implemented algorithms:
- 2D Fenwick tree implementation using static arrays.
- Point updates or range queries are handled in O(log^2(N)).
- ~5x faster than pointer implementation
- Finding Articulation points and bridges of graphs
- Linear time implementation
- Binary trie using static arrays
- Implementation can be modified for larger alphabets
- ~4x faster than pointer implementation
- Building Cartesian trees in linear time
- Finding the closest points in a set of 2D points in O(N * log(N))
- Decart tree with data references
- Please, refer to the problem on the link in the file to understand what type of queries need to be handled
- Expected O(log(N)) time approach to handle standard BST operations
- Extra tree and dynamic array operations
- Dijkstra with Min-Heap:
- Manual implementation of the heap
- Finding dynamic median:
- Logarithmic solution to find median during series of update operations
- Fast ternary search
- O(log(2)(N)) performance instead of classic O(log(3/2)(N))
- Fibonacci matrix
- 2x2 matrix implementation to calculate N-th Fibonacci number in O(log(N))
- Implicit segment tree implementation
- It's pointer implementation, using the same approach in [1], static array implementation can be produced.
- Update/Ask queries in O(log(RANGE))
- Johnson's all pairs shortest path problem
- O(V * E * log(V)) overall complexity
- Bellman-Ford algorithm is used to detect negative cycle(if any).
- Karatsuba multiplication in O(N^1.58)
- multiplication of large integers (big integer in CP)
- Although FFT is O(N * log(N)), Karatsuba is handy when you do not have prewritten FFT code.
- Kruskal Minimal Spanning Tree Algorithm in O(E * log(V))
- Union/Find data structure
- Atkin's prime sieve in O(N)
- Atkin's wheel ("WHEEL" variable in the code) can be adjusted
- Linear prime sieve
- MO's algorithm
- Offline query handling
- Finding farthest points based on Manhattan distance in 2D grid
- O(N * log2(N))
- can be extended to larger dimensions O(N * 2^d * log2(N))
- Miller-Rabin primality test
- Ordered set - Decart tree
- Just more powerful than a BST
- Persistent segment tree implementation
- static array implementation
- finding Kth element in any sorted subarray of elements in O(log(N))
- Hash table for comparing range of fixed objects
- Rope - builtin decart tree
- Basic String matching utilities
- Z function
- prefix function
- KMP algorithm
- Fast/ultrafast input & output for enermous input
- getchar_unlocked() will probably produce some warnings (unsafe blabla...), you may replace it with getchar()
- Multiplication bases and modulos for hash tables
- A method to hack unordered_set solutions during competitions
- The solution belongs to a coder who hacked my solution during one of Codeforces contests)
- Quicksort hack by Halyavin
- Some people still use qsort() function in C. The code produces adversary test cases.
- Quadtree implementation for 2D aggregate queries
- LCA with binary lifting
- Preprocessing in O(N * log(N))
- LCA queries in O(log(N))
- Triangle counting in general graphs O(M^1.5)
- M is the number of edges
- Min-Stack: finding minimum elements in stack in O(1)
- Huffman encoding via priority queues