Heavy-Light Decomposition for Range Queries on Trees
Dynamic operations that mix path updates and queries on a tree defeat simple prefix‑sum or difference‑based preprocessing. Heavy‑light decomposition (HLD) assigns each vertex to a heavy path and gives every path, as well as every complete subtree, a contiguous interval in a preorder. By flattening t...