Изменения
→The Macro-Micro-Tree Algorithm
*Зададим некую функцию <tex>S(n) = \dfrac{1}{4} \log n</tex>
*Посчитаем размер поддерева для каждой вершины с помощью обхода в глубину, после чего удалим все вершины размер поддерева которых меньше чем <tex>S(n)</tex>.
*Забудем на время про удаленные поддеревья, для оставшегося дерева наш алгоритм даст работает за < <tex>O(\dfrac{n}{S(n)} \log n + n), O(1)</tex> >. Что дает нам алгоритм за< <tex>O(n), O(1) </tex>>. Для удаленных поддеревьев же выполним полный предподсчет: таких деревьев не более чем <tex>2^{2S(n)}</tex>, что дает ассимптотику предподсчета
<tex>O(\sqrt{n} \log^2{n}) = o(n) = O(n)</tex>.
В итоге полученный алгоритм действительно работает за <<tex>O(n), O(1)</tex>>.
== Источники информации ==
*https://www.cadmo.ethz.ch/education/lectures/HS18/SAADS/reports/5.pdf
*https://en.wikipedia.org/wiki/Level_ancestor_problem
