Concepts5

Dominator Tree

A dominator tree summarizes “must-pass” relationships in a directed graph from a chosen root r: u dominates v if every path from r to v goes through u.

#dominator tree#lengauer tarjan#semidominator+10

🗂️Data StructureAdvanced

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.

#link-cut tree#dynamic tree#splay tree+12

🗂️Data StructureAdvanced

Centroid Decomposition

Centroid decomposition splits a tree around a special node (centroid) so that every remaining component has at most half the nodes.

#centroid decomposition#centroid tree#tree algorithms+11

🗂️Data StructureAdvanced

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.

#heavy light decomposition#hld#path query+12

🗂️Data StructureIntermediate

Sparse Table

A Sparse Table is a static range-query data structure that preprocesses an array in O(n \log n) time and answers many queries in O(1) time.

#sparse table#range minimum query#rmq+12