Heavy Light Decomposition

Definition

Suppose we are given a tree $G$ with $n$ vertices and an arbitrary chosen root.

The idea of heavy-light decomposition is to split the tree into several disjoint paths so that from any vertex to the root, we pass through at most $O(\log n)$ different paths.

This is useful because many queries on a tree path, such as:

• sum on the path from $a$ to $b$;
• maximum on the path;
• updates on the path,

can then be reduced to several queries on ordinary array segments.

Idea

For each vertex $$, let be the size of its subtree, that is, the number of vertices in the subtree of , including itself.