1632
правки
Изменения
м
rollbackEdits.php mass rollback
'''Задача о уровне предка''' — (англ. "Level Ancestor problem") является задачей о превращении данного подвешенного дерева <tex>T</tex> в структуру данных, которая сможет определить предка любого узла на заданном расстоянии от корня дереваэтого узла.
{{Задача
Это улучшение Longest-path декомпозиции, позволяющее, как мы потом докажем, подниматься на любую высоту за <tex>O(1)</tex>. Выполним его следующим образом: увеличим каждый путь в два раза вверх, для каждого нового пути сохраним все входящие в него вершины,
а для каждой вершины сохраним ее номер в пути, в который она входит. Построение обычной longest-path декомпозиции займет у
нас <tex>O(n)</tex> времени (обход в глубину), соответственно удлиннение удлинение каждого пути не ухудшит асимптотику до <tex>O(n \log n)</tex>.
После этого посчитаем двоичные подъемы для каждой вершины за <tex>O(\log n)</tex>, что соответственно не ухудшит асимптотикуполучим итоговую оценку <tex>O(n \log n)</tex> на предподсчет.
=== Псевдокод ===
i = <tex>\lfloor \log_2 n \rfloor</tex>
v = p[i][v] ''<font color="green">// делаем максимально большой прыжок вверх</font>''
i = n - <tex>2^i </tex> ''<font color="green">// на столько осталось еще подняться</font>''
'''return''' ladder[way[v]][num[v] - i] ''<font color="green">// так как теперь <tex>v</tex> и ответ находятся на одном пути</font>''
В данном разделе мы докажем, что предподсчет предыдущего алгоритма можно улучшить до <tex>O(n)</tex>.
Для начала рассмотрим алгоритм <tex>\langle O(L\log n + n), O(1)\rangle </tex>, где <tex>L</tex> это количество листьев.
*С помощью обхода в глубину запомним по одному листу в ее поддереве для каждой вершины
*Воспользуемся алгоритмом лестниц, но будем выполнять предподсчет только для листьев.
Рассмотрим как можно улучшить данный алгоритм:
