Изменения
Нет описания правки
Таким образом, наш алгоритм работает за < <tex>O(n\log n), O(1)</tex> >. Методом четырех русских данный метод можно улучшить до < <tex>O(n), O(1)</tex> > с помощью оптимизации предподсчета.
== The Macro-Micro-Tree Algorithm ==
В данном разделе мы докажем, что предподсчет предыдущего алгоритма можно улучшить до <tex>O(n)</tex>.
Для начала рассмотрим алгоритм за < <tex>O(L\log n + n), O(1)</tex> >, где <tex>L</tex> это количество листьев.
*С помощью обхода в глубину запомним по одному листу в ее поддереве для каждой вершины
*Воспользуемся алгоритмом лестниц, но будем выполнять предподсчет только для листьев.
Рассмотрим как можно улучшить данный алгоритм:
*Зададим некую функцию <tex>S(n) = \dfrac{1}{4} \log n</tex>
*Посчитаем размер поддерева для каждой вершины с помощью обхода в глубину, после чего удалим все вершины, размер поддерева которых меньше чем <tex>S(n)</tex>.
*
