188
правок
Изменения
Нет описания правки
cells[v].add(newCell)
layer++
==Операции удаления и добавления ребра==
Как только некоторая вершина помечается как изменившаяся, отменим её действие на таблицу. А именно, найдем момент времени, когда вершина сжимается к родителю. Рассмотрим, какие вершины поменяются при сжатии данной. Это ее родитель (если он есть), а также сын (если он есть). Для каждой из этих вершин поменяем значения изменений, которые необходимо применить к состоянию. Также пометим, что эти вершины поменялись на этом слое. Для этого на каждом слое будем хранить список вершин, которые на нем поменялись. А перед тем как обрабатывать очередной слой будем добавлять в множество изменившихся вершин вершины из соответствующего списка. Кроме удаления эффекта от изменившихся вершин также необходимо и добавить правильный эффект. Для этого будем для каждой из из- менившихся вершин определять, как ее состояние меняется при переходе к следующему слою. Если вершина сжимается к ее родителю, то пометим родителя и ребенка (если он есть) и поменяем изменение, которое хранится в соответствующих клетках. А для пересчета состояния клеток воспользуемся значениями изменений, которые сохранены в клетках.<br>
Рассмотрим, что происходит с таблицей при изменении одного ребра. Основная идея заключается в том, чтобы научится пересчитывать все изменения таблицы за время пропорциональное их количеству. Для этого будем эффективно поддерживать множество изменившихся клеток. В момент, когда вершина помечается, как изменившаяся, найдем, как она влияет на таблицу и отменим это влияние. <br>Для начала необходимо найти момент времени, когда вершина сжимается. В этот момент она влияет на не более чем две вершины. Изменим значения <tex>\mathrm{cntChild}</tex>, <tex>\mathrm{sumChild}</tex> и <tex>\mathrm{newParent}</tex> нужным образом. Также необходимо добавить эти вершины в множество изменившихся (в момент, когда будет обработан соответствующий слой). Поэтому, для каждого слоя еще будем хранить список вершин, которые должны быть помечены перед обработкой слоя.<br>Алгоритм обновления дерева:
'''func''' changeTree(<tex>(u, v)</tex>: '''Edge''')''':'''
time = time + 1
affected = <tex>\emptyset</tex>
markAffected(u) <font color="green">// пусть из дерева было удалено ребро <tex>(u, v)</tex></font>
markAffected(v)
cells[u].parent = u
cells[v].cntChild--
cells[v].sumChild -= u
layer = 0
'''while''' <tex>\mathrm{affected} \neq \emptyset</tex>
'''for''' <tex>v \in \mathrm{affectedOnLayer}</tex>
markAffected(v)
'''for''' <tex>v \in \mathrm{affected}</tex>
c = getCellForVertex(v)
'''if''' shouldRemoveVertex(v)
cells[v].size = layer + 1
'''if''' c.cntChild == 1
getCellForVertex(c.sumChild).newParent = c.parent
getCellForVertex(c.parent).addChild(c.sumChild)
markAffected(c.sumChild)
'''if''' c.parent <tex>\neq</tex> v
getCellForVertex(c.parent).removeChild(v)
markAffected(c.parent)
affected.remove(v)
'''for''' <tex>v \in \mathrm{affected}</tex>
newCell = getCellForVertex(v).clone().applyChanges()
cells[v][layer + 1] = newCell
layer++
'''func''' markAffected(v: '''int''')''':'''
'''if''' lastUpdateTime[v] == time
'''return''' <font color="green">// вершина уже помечена</font>
lastUpdateTime[v] = time
affected.add(v)
removeEffectOfVertex(v)
'''func''' removeEffectOfVertex(v: '''int''')''':'''
layer = cells[v].size
c = cells[v][layer]
'''if''' c.parent == v
'''return'''
cells[c].parent.removeChild(v)
'''if''' c.cntChild == 1
cells[c.parent].addChild(c.sumChild)
cells[c.sumChild].newParent = v
==Возможность параллельного построения==
