icpc-notebook

Overview

This is a notebook for competitive programming. It contains implementations of various algorithms and data structures, as well as some useful macros and tricks.

Note: This notebook is still a work in progress. Some sections are incomplete or missing.

Currently working on Geometry section and will soon publish it.

Table of Contents

• Data Structures

  • Binary Indexed Tree
  • Li Chao Tree
  • Link-Cut Tree
  • Merge Sort Tree
  • Mo's Algorithm
  • Segment Tree
  • Sparse Table
  • Square Root Decomposition
  • Wavelet Tree

• Graphs

  • Bridge Tree
  • Dijkstra's Algorithm
  • Dinic's Algorithm
  • Disjoint Set Union
  • EERTree
  • Heavy-Light Decomposition
  • Kruskal's Algorithm
  • Lowest Common Ancestor
  • Maximum Flow
  • Shortest Path Faster Algorithm
  • Tarjan's Algorithm
  • Strongly Connected Components

• Math

  • Chinese Remainder Theorem
  • Combinatorics
  • Convex Hull Trick
  • Fast Fourier Transform
  • Gaussian Elimination
  • Miller-Rabin Primality Test
  • Pollard's Rho Algorithm
  • Sieve of Eratosthenes
  • Simplex Algorithm
  • Sparse Matrix
  • Strassen's Algorithm

• Strings

  • Aho-Corasick Algorithm
  • Knuth-Morris-Pratt Algorithm
  • Manacher's Algorithm
  • Suffix Array
  • Suffix Automaton
  • Z Algorithm
  • String Hashing
  • Trie
  • Suffix Tree
  • Suffix Automaton

• Game Theory

  • Grundy Numbers
  • Nim Game
  • Sprague-Grundy Theorem

• Miscellaneous

  • Arpa's Trick
  • Matrix Exponentiation
  • Parellel Binary Search
  • Rerooting Technique
  • Small to Large Technique

Contributing

If you find any bugs or have any suggestions, feel free to create an issue or submit a pull request.

Acknowledgements

• cp-algorithms
• e-maxx-eng

Thanks for checking out this notebook! If you found it helpful, please give it a star ⭐️