188
правок
Изменения
Нет описания правки
layer++
===Операции удаления и добавления ребра===
Как только некоторая вершина помечается как изменившаяся, отменим её действие на таблицу. А именно, найдем :# Найдем момент времени, когда вершина сжимается к родителю. # Рассмотрим, какие вершины поменяются при сжатии данной. Это : это ее родитель (если он есть), а также сын (если он есть). Для каждой из этих вершин поменяем значения изменений, которые необходимо применить к состоянию. Также пометим# Пометим, что эти вершины поменялись на этом слое. Для этого на каждом слое будем хранить список вершин, которые на нем поменялись. А перед тем как обрабатывать очередной слой будем добавлять в множество изменившихся вершин вершины из соответствующего списка. # Кроме удаления эффекта от изменившихся вершин также необходимо и добавить правильный эффект. Для этого будем для каждой из из- менившихся изменившихся вершин определять, как ее состояние меняется при переходе к следующему слою. Если вершина сжимается к ее родителю, то пометим родителя и ребенка (если он есть) и поменяем изменение, которое хранится в соответствующих клетках. А для пересчета состояния клеток воспользуемся значениями изменений, которые сохранены в клетках.<br>
Рассмотрим, что происходит с таблицей при изменении одного ребра. Основная идея заключается в том, чтобы научится пересчитывать все изменения таблицы за время пропорциональное их количеству. Для этого будем эффективно поддерживать множество изменившихся клеток. В момент, когда вершина помечается, как изменившаяся, найдем, как она влияет на таблицу и отменим это влияние. <br>Для начала необходимо найти момент времени, когда вершина сжимается. В этот момент она влияет на не более чем две вершины. Изменим значения <tex>\mathrm{cntChild}</tex>, <tex>\mathrm{sumChild}</tex> и <tex>\mathrm{newParent}</tex> нужным образом. Также необходимо добавить эти вершины в множество изменившихся (в момент, когда будет обработан соответствующий слой). Поэтому, для каждого слоя еще будем хранить список вершин, которые должны быть помечены перед обработкой слоя.<br>Алгоритм обновления дерева:
'''func''' changeTree(<tex>(u, v)</tex>: '''Edge''')''':'''
