Concepts113
Category
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.
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.
Centroid Decomposition
Centroid decomposition splits a tree around a special node (centroid) so that every remaining component has at most half the nodes.
HLD - Path Queries and Updates
Heavy-Light Decomposition (HLD) breaks a tree into a small number of vertical chains so any path (u,v) becomes O(log n) contiguous segments in an array.
Wavelet Tree
A wavelet tree is a recursive data structure built over a sequenceβs alphabet that answers rank, select, and quantile (k-th smallest) queries in O(log Ο) time, where Ο is the number of distinct values.
Heavy-Light Decomposition
Heavy-Light Decomposition (HLD) breaks a tree into O(n) disjoint chains so that any root-to-node path crosses only O(log n) chains.
Persistent Array and Treap
Persistence lets you keep every past version of a data structure while making O(log n) updates and queries on any version.
Splay Tree
A splay tree is a self-adjusting binary search tree that moves the most recently accessed node to the root with rotations.
Implicit Treap
An implicit treap is a randomized balanced binary tree that treats array positions as keys without storing them explicitly.