Задача поиска предка на уровне (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)
• Микро-макро эвристика

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