Изменения
→Модификация предподсчета за O(n) времени и O(n) памяти
==Модификация предподсчета за O(n) времени и O(n) памяти==
Воспользуемся идеей [[Heavy-light декомпозиция|Heavy-light декомпозиции]], которая разбивает все вершины дерева на вершинно-непересекающиеся пути так, что поднимаясь от любой вершины до корня дерева придется сменить не более <tex>\log(n)</tex> различных путей.
===Препроцессинг===
* '''Память''': Для реализации алгоритма требуется <tex>O(n)</tex> памяти.
* '''Препроцессинг''': Heavy-light декомпозиция строится за <tex>O(n)</tex>.
* '''Запросы''': По свойству heavy-light декомпозиции, на пути от вершины к корню мы сменим не более <tex>\log(n)</tex> путей. Значит время выполнения запроса также <tex>O(\log(n))</tex>.
==См. также==
