Concepts318
Category
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.
Persistent Segment Tree
A persistent segment tree stores every historical version of an array-like data while supporting queries and updates in O(log n) time.