188
правок
Изменения
Нет описания правки
lastUpdateTime[i] = 0
cells[i] = []
Кроме запросов о структуре леса, Rake-Compress деревья можно использовать для подсчета значений некоторых функций. Например, каждой вершине можно сопоставить некоторое значение и узнавать, чему равна сумма значений всех вершин, которые находятся в поддереве.
Для этого в клетках таблицы Rake-Compress дерева необходимо хранить не только состояние вершины, но и значение функции, посчитанной на части дерева, которое уже было сжато в вершину. Если функция является аддитивной, то ее пересчет аналогичен пересчету множества детей вершины. Так, если некоторая вершина сжимается к родителю, то в соответствующей родителю клетке необходимо обновить значение функции. При добавлении и удалении ребер необходимо в изменившихся клетках пересчитывать значение функции.
===Построение===
==Возможность параллельного построения==
Операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> можно выполнять параллельно для всех вершин. Если предположить, что множество детей можно пересчитывать за <tex>O(1)</tex>, то Rake-Compress дерево можно построить за <tex>O(\log{n})</tex> в модели PRAM в случае наличия <tex>\Omega(n)</tex> процессоров.
==Применения==
