Что: Лекция
Когда: Четверг, 16 марта 2017, 18:30–19:50
Где: Таймс, ауд. с чёрными досками

Описание

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

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

Link-Cut деревья

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