Изменения
→Сравнение с наивными реализациями
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.
== См. также ==
