Heavy-Light, Link-Cut

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

• Поиск минимума на пути в дереве
• Статическая задача: двоичные подъемы
• Тяжелые и легкие ребра
• Разбиение на тяжелые пути
• Оценка $log(n)$ на число легких ребер
• Финальная оценка $log^2(n)$

Link-Cut деревья

• Операции link и cut
• Использование деревьев по неявному ключу
• Амортизированная оценка $log^2(n)$
• Использование splay-деревьев для улучшения времени до $log(n)$