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

Четверг, 03 марта 2016
Таймс, ауд. 404

Описание

Задача поиска предка на уровне (Level Ancestor Problem)

  • Двоичные подъемы: O(log n) на запрос + O(N log N) предпосчет
  • Лесенки: O(log n) на запрос + O(N) предпосчет
  • Двоичные подъемы + Лесенки: O(1) на запрос + O(N log N) предпосчет
  • Идея уменьшить число прыжковых вершин до O(N / log N)
  • Микро-макро эвристика

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

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