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

⚙️AlgorithmAdvanced

Virtual Tree (Auxiliary Tree)

A Virtual Tree (Auxiliary Tree) compresses a large tree into a much smaller tree that contains only the k important nodes and the LCAs needed to keep them connected.

#virtual tree#auxiliary tree#lca+12

⚙️AlgorithmIntermediate

Lowest Common Ancestor (LCA)

The Lowest Common Ancestor (LCA) of two nodes in a rooted tree is the deepest node that is an ancestor of both.

#lowest common ancestor#binary lifting#euler tour+12

⚙️AlgorithmIntermediate

DFS - Tree and Graph Properties

Depth-First Search (DFS) assigns each vertex a discovery time and a finish time that capture a neat nesting structure of recursion.

#dfs#timestamps#discovery time+11

🗂️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