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

Понедельник, 23 февраля 2015
Таймс, ауд. 404

Описание

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

http://courses.csail.mit.edu/6.851/spring14/scribe/lec15.pdf