Concepts25
Category
Top Tree
Top trees are dynamic tree data structures that represent a forest as a hierarchy of clusters, allowing O(log n) amortized time for link, cut, path queries/updates, and many subtree queries.
Kinetic Tournament Tree
A kinetic tournament tree maintains the minimum (or maximum) of moving values whose pairwise order can change over time.
Aho-Corasick - DP Applications
Aho–Corasick (AC) turns a set of forbidden patterns into a finite automaton that lets you process or generate strings while tracking whether any pattern appears.
Li Chao Tree
A Li Chao tree maintains a set of lines y = m x + b and answers minimum (or maximum) value queries at a given x in O(log C) time, where C is the numeric range of x.
Palindromic Tree (Eertree)
A Palindromic Tree (Eertree) stores every distinct palindromic substring of a string as a node and can be built online in linear time.
Suffix Automaton - Advanced Usage
A suffix automaton (SAM) is a compact DFA that captures all distinct substrings of a string and supports many advanced queries in linear time.
Suffix Automaton
A suffix automaton (SAM) is the minimal deterministic finite automaton that recognizes all substrings of a string, built online in O(n) time and space.
Aho-Corasick Automaton
Aho–Corasick is a trie with failure links that finds all occurrences of many patterns in a single pass over the text.
Suffix Array - LCP Array Applications
The LCP (Longest Common Prefix) array, built alongside a suffix array, unlocks fast solutions to problems like longest repeated substring, number of distinct substrings, and longest common substring.
Euler Tour Tree
An Euler Tour Tree represents each rooted tree as a DFS open/close sequence so that every subtree is a single contiguous interval.
Suffix Array
A suffix array stores the starting indices of all suffixes of a string in lexicographic order.
Link-Cut Tree
A Link-Cut Tree (LCT) maintains a dynamic forest and supports link, cut, and path queries in O(log n) amortized time.