Heavy-Light, Link-Cut

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

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

Link-Cut деревья

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