186
правок
Изменения
м
→Варианты хранения центроидной декомпозиции
Этот подход уступает в количестве необходимой дополнительной памяти (<tex>O(n \cdot log(n))</tex> суммарно), но имеет ряд преимуществ :
1) При проходе по массиву предков фиксированной вершины будет выигрыш в скорости работы, т.к. весь массив будет лежать непрерывным блоком данных и следовательно будет закэширован
2) На массиве предков можно строить различные структуры данных (такие как, например, дерево отрезков) для быстрого (в случае с деревом отрезков <math>O(log(log(n)))</math> на запрос) поиска предка с необходимыми свойствами. Так, например, в описанной выше задаче про помеченные вершины наибольшего общего предка можно искать методом двоичных подъемов за <math>O(log(log(n))</math> на запрос, т.к. размер массива предков есть <math>O(log(n))</math> (по свойству 1 центроидной декомпозиции). Используя эту оптимизацию можно получить время <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> времени.
==См. также==
