Изменения
→Сравнение с наивными реализациями
запрос можно улучшить до <tex>O(\log n)</tex> c помощью [[Метод двоичного подъёма | предподсчета двоичных подъемов]] ,
но тогда и время предподсчета в наивной реализации (посчитать подъемы для всех вершин) ухудшится до < <tex>O(n \log n),
O(\log n)</tex> > времени и <tex>O(n \log n)</tex> памяти. А Также альтернативой данным двум алгоритмам является полный предподсчет всех возможных запросов, что соответственно дает нам асимптотику < <tex>O(n^2), O(1)</tex> > времени и <tex>O(n^2)</tex> памяти.
Таким образом самым оптимальным из описанных как по времени, так и по памяти является алгоритм Macro-Micro-Tree.
