Luzhiled's memo

Luzhiled’s memo I often refer to it because it’s a useful and concise discussion of computational quantities.

graph - Euler path (Eulerian-Trail) - Width-first search on grid (Grid-BFS) - Hungarian law (Hungarian) - Maximum matching of bipartite graphs (Bipartite-Matching) - Maximum matching of bipartite graphs (Hopcroft-Karp) - double edge connected component decomposition (Two-Edge-Connected-Components) - double vertex connected component decomposition (Bi-Connected-Components) - all-points-between shortest path (Warshall-Floyd) - single origin shortest path (Bellman-Ford) - Single-start shortest path (Dijkstra) - Single starting point shortest path (SPFA) - strongly-coupled component decomposition (Strongly-Connected-Components) - number of colors (Chromatic-Number) - Maximum Creek (Maximum-Clique) - maximum flow (Dinic) - Maximum flow (Ford-Fulkerson) - Maximum flow (Push-Relabel) - maximal independent set (Maximum-Independent-Set) - arbitrary arbitrary wooden rule that forbids the use of the smallest possible distance between two objects (e.g. mountains) (Chu-Liu/Edmond) - minimum area tree (Borůvka) - Minimum area tree (Kruskal) - Min. whole area tree (Prim) - Maximum flow with minimum flow limitation - least-cost current (Primal-Dual) - joint point (LowLink)

data structure

• [BIT]
• Binary-Trie
• Convex-Hull-Trick-Add-Monotone
• Li-Chao-Tree
  • Link-Cut Tree Sub-tree Query (Link-Cut-Tree-Subtree)
  • Link-Cut Tree (Link-Cut-Tree)
  • wavelet matrix (Wavelet-Matrix)
  • sparse table (Sparse-Table)
  • Sum of k ascending sliding intervals (Priority-Sum-Structure)
  • segment tree (Segment-Tree)
  • tri-tree (Trie)
  • mergeable heap (Skew-Heap)
  • Square partitioning of columns (Sqrt-Decomposition)
  • equilibrium binary search tree (RBST)
  • Equilibrium binary search tree (Red-Black-Tree)
  • continuous array (Persistent-Array)
  • prime set data structure (UnionFind)

character string - rolling hash (Rolling-Hash) - suffix array (Suffix-Array) - Longest Common Prefix (Z-Algorithm) - long sentence (Manacher) palindrome - Multiple String Search (Aho-Corasick)

tree - HL Disassembly (Heavy-Light-Decomposition) - omni-directional wooden DP (ReRooting) - least common ancestor (Doubling-Lowest-Common-Ancestor) - Diameter of tree (Tree-Diameter) - Decomposition of the center of gravity of a tree (Centroid-Decomposition) - Converted to rooted trees (Convert-Rooted-Tree)

mathematics

• Mod-Int
• Power (Mod-Pow)
  • Euler’s φ function (Euler’s-Phi-Function)
  • Euler’s φ function table (Euler’s-Phi-Function-Table)
  • number of bells (Bell-Number)
  • Lagrangian interpolation (Lagrange-Polynomial)
  • binomial coefficient (Binomial)
  • binomial coefficient table (Binomial-Table)
  • Arbitrary mod convolution (Arbitrary-Mod-Convolution)
  • number of divisions (Partition)
  • Split Number Table (Partition-Table)
  • quotient list (Quotient-Range)
  • formal power series (Formal-Power-Series) formal power series
  • Extended Euclidean reciprocal division (Extended-Euclidean-Algorithm) Extended Euclidean reciprocal division
  • Type 2 Sterling Number (Stirling-Number-Of-The-Second-Kind)
  • irreducible enumeration (Divisor)
  • prime factor decomposition (Prime-Factor)
  • prime table (Prime-Table)
  • prime factor determination (Is-Prime)
  • combination (Combination)
  • matrix operation (Matrix)
  • radix (numeration) conversion (Convert-Base)
  • factorial (Factorial)
  • Discrete Logarithm Problem (Mod-Log)
  • Fast Fourier Transform (Fast-Fourier-Transform)

dynamic programming

• Divide-And-Conquer-Optimization
• Monotone-Minima
  • Slide Minimum (Slide-Min)
  • 1D cumulative sum (Cumulative-Sum)
  • two dimensional cumulative sum (Cumulative-Sum-2D)
  • Knapsack with a limited number of knapsacks (Knapsack-Limitations)
  • maximum rectangle (Largest-Rectangle)
  • optimal binary search tree (Hu-Tucker)
  • LAM (Longest-Increasing-Subsequence)

memo - doubling - principle of inclusion - Burn Bury Issue bury in the fire - embarrassingly bad video game where the object is to make the audience laugh

Other

• Mo’s Algorithm

• Offline-Dynamic-Connectivity

  • If the edge add/delete query is given offline, it can be handled efficiently by using Undoable Union-Find.

  • coordinate compression (Compress)

• algorithm

---

This page is auto-translated from [/nishio/Luzhiled’s memo](https://scrapbox.io/nishio/Luzhiled’s memo) using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.