36
правок
Изменения
→Доказательство корректности
=== Доказательство корректности ===
Рассмотрим путь, на котором лежит вершина <tex>v</tex> до удвоения. Он длины хотя бы <tex>2^i</tex>, так как мы точно знаем, что существует вершина потомок <tex>v</tex>, расстояние до которого ровно <tex>2^i</tex> (это вершина, из которой мы только что пришли). Значит, после удвоения этот путь стал длины хотя бы <tex>2^{i + 1}</tex>, причем хотя бы <tex>2^i</tex> вершин в нем - — предки <tex>v</tex>. Это означает, что вершина, которую мы ищем, находится на этом пути (иначе бы мы могли до этого прыгнуть еще на <tex>2^i</tex> вверх). Так как мы знаем позицию <tex>v</tex> в этом пути, то нужную вершину мы можем найти за <tex>O(1)</tex>.
Таким образом, наш алгоритм работает за <tex>\langle O(n\log n), O(1)\rangle </tex> времени и за <tex>O(n\log n)</tex> памяти. Методом четырех русских данный метод можно улучшить до <tex>\langle O(n), O(1)\rangle </tex> с помощью оптимизации предподсчета.
== The Macro-Micro-Tree Algorithm ==
В данном разделе мы докажем, что предподсчет предыдущего алгоритма можно улучшить до <tex>O(n)</tex>.
