Concepts40
Sqrt Tree
A sqrt tree is a layered block-decomposition data structure that answers range queries in O(1) time after O(n \log \log n) preprocessing.
Segment Tree with Range Affine Transformation
A segment tree with lazy propagation can support range updates of the form x → a·x + b (affine transformations) and range-sum queries in O(log n) per operation.
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.
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.
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.
Centroid Decomposition - Distance Queries
Centroid decomposition splits a tree into levels by repeatedly removing a centroid so that each remaining component is at most half the size.