186
правок
Изменения
→Варианты реализации
Итак, мы научились решать задачу с <math>O(n)</math> дополнительной памятью и временной сложностью <math>O(log^2(n))</math> на запрос любого типа с предварительным предпосчетом за <math>O(n)</math>.
== Варианты реализации хранения центроидной декомпозиции ==Для хранения дерева центроидов <math>T</math> есть <math>2</ TODO math> подхода, имеющих свои преимущества и недостатки :: написать про то * Для каждой вершины <math>v</math> исходного дерева запомним величину <math>p_v</math> - номер предка вершины <math>v</math> в дереве <math>T</math>. Этот подход наиболее экономный по памяти (<math>O(n)</math>), что можно но уступает в скорости и функциональности. * Для каждой вершины <math>v</math> исходного дерева будем хранить весь массив предков <math>p[v]</math> в дереве центроидов. Этот подход уступает в количестве необходимой дополнительной памяти (+память О<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*logn))</math> на запрос.
==См. также==
