Concepts40
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.
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.
Treap
A treap is a binary search tree on keys combined with a heap on random priorities, which keeps the tree balanced in expectation.
Merge Sort Tree
A Merge Sort Tree is a segment tree where every node stores the sorted list of values in its segment.
Sqrt Decomposition
Sqrt decomposition partitions an array into about \(\sqrt{n}\) blocks, each of size about \(\sqrt{n}\), to speed up range queries and updates.
Iterative Segment Tree
An iterative segment tree stores all leaves in tree[n..2n-1] and internal nodes in tree[1..n-1], enabling O(\log n) point updates and range queries without recursion.
Segment Tree Beats
Segment Tree Beats is a segment tree variant that supports range chmin/chmax (clamping) together with queries like range sum, min, and max in amortized logarithmic time.
Binary Trie for XOR
A binary trie (also called a bitwise trie) stores numbers by their binary bits, branching on 0/1 at each level.
Segment Tree - Handling Multiple Lazy Operations
When a segment tree supports multiple range updates, you must define how lazy tags compose, because the order of operations matters and composition is not commutative.