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