Heavy-Light декомпозиция

Определение

Предположим, нам дано дерево $G$ с $n$ вершинами и произвольно выбранным корнем.

Идея Heavy-Light декомпозиции состоит в том, чтобы разбить дерево на несколько непересекающихся путей так, чтобы от любой вершины до корня мы проходили не более чем через $O(\log n)$ различных путей.

Это полезно, потому что многие запросы на пути в дереве, такие как:

• сумма на пути от $a$ до $b$;
• максимум на пути;
• обновления на пути,

затем могут быть сведены к нескольким запросам на обычных отрезках массива.

Идея

Для каждой вершины $$ пусть — размер её поддерева, то есть число вершин в поддереве , включая саму .