36
правок
Изменения
→Сравнение с наивными реализациями
но тогда и время предподсчета в наивной реализации (посчитать подъемы для всех вершин) ухудшится до <tex>\langle O(n \log n),
O(\log n)\rangle </tex> времени и <tex>O(n \log n)</tex> памяти. Также альтернативой данным двум алгоритмам является полный предподсчет всех возможных запросов, что соответственно дает нам асимптотику <tex>\langle O(n^2), O(1)\rangle </tex>времени и <tex>O(n^2)</tex> памяти.
Сравнение различных асимптотик из данной статьи:
<center>
{| class="wikitable" align="centerleft" style="margin:auto; color: blue; background-colorclear:#ffffffboth;" cellpadding="10"
|+
|-align="center"
|-align="center"
!Обычный подьем до нужного уровня
