Изменения

# На массиве предков можно строить различные структуры данных (такие как, например, дерево отрезков) для быстрого (в случае с деревом отрезков <math>O(log(\log(n)))</math> на запрос) поиска предка с необходимыми свойствами. Так, например, в описанной выше задаче про помеченные вершины наибольшего общего предка можно искать методом двоичных подъемов за <math>O(\log(\log(n))</math> на запрос, так как размер массива предков есть <math>O(\log(n))</math> (по свойству <math>1</math> центроидной декомпозиции). Используя эту оптимизацию можно получить время <math>O(\log(n)) + O(log(\log(n)) = O(\log(n))</math> на запрос нахождения ближайшей помеченной вершины. Чтобы добиться улучшенной асимптотики для запросов изменения можно хранить дерево отрезков на каждом из путей <math>p[v]</math>, в каждой вершине которого хранить двоичное дерево поиска и поддерживать отложенные операции. Тогда ответ на эти запросы будет занимать <math>O(\log(n) \cdot \log(\log(n))</math> времени.