Изменения

'''Динамическая связность''' (англ. ''dynamic connectivity'') {{---}} задача обработки Задача|definition = Имеется [[Основные_определения:_граф,_ребро,_вершина,_степень,_петля,_путь,_цикл#Неориентированные_графы|неориентированный граф]] из <tex>n</tex> вершин, изначально не содержащий рёбер. Требуется обработать <tex>m</tex> запросов на добавление трёх типов:* добавить ребро между вершинами <tex>u</tex> и <tex>v</tex>,* удалить ребро между вершинами <tex>u</tex> и удаление рёбер в неориентированном графе<tex>v</tex>, а также проверки* проверить, лежат ли какие-то вершины <tex>u</tex> и <tex>v</tex> в одной компоненте связности.В графе могут быть кратные рёбра и петли.}}

Если нет удалений рёбер, задачу можно решить при помощи [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]]: каждая . Каждая компонента связности {{---}} это одно множество в СНМ, и при добавлении рёбер они объединяются.

Построим на массиве запросов [[Дерево отрезков. Построение|дерево отрезков]], в каждой его вершине будем хранить список пар. Каждый из отрезков <tex>i</tex>-е рёбро графа нужно добавить на отрезок <tex>[L_i,R_i]</tex> разобьём на отрезки, соответствующие вершинам дерева отрезков (. Это делается аналогично тому, как выполняется запрос в дереве отрезков происходит добавление на отрезке (процесс описан в дереве отрезковстатье "[[Несогласованные поддеревья. Реализация массового обновления]]") , но без <tex>push</tex>: нужно спуститься по дереву от корня и запишем в соответствующие вершины записать пару <tex>u_i,v_i</tex> (в каждой вершине вершины дерева хранится массив пар)отрезков.  Теперь чтобы узнать, какие рёбра существуют во время выполнения <tex>i</tex>-го запроса, достаточно посмотреть на путь от корня дерева отрезков до листа, который соответствует этому запросу {{---}} рёбра, записанные в вершинах этого пути, существуют во время выполнения запроса. === Ответы на запросы ===Обойдём дерево отрезков в глубину, начиная с корня. Будем поддерживать граф, состоящий из рёбер, которые содержатся на пути от текущей вершины дерева отрезков до корня. При входе в вершину добавим в граф рёбра, записанные в этой вершине. При выходе из вершины нужно откатить граф к состоянию, которое было при входе. Когда мы добираемся до листа, в граф уже добавлены все рёбра, которые существуют во время выполнения соответствующего запроса, и только они. Поэтому если этот лист соответствует запросу третьего типа, его следует выполнить и сохранить ответ.

Будем Для поддержания такого графа и ответа на запросы будем использовать [[СНМ (реализация с помощью леса корневых деревьев)|систему непересекающихся множеств. Обойдём дерево отрезков в глубину, начиная с корня]]. При входе добавлении рёбер в вершину добавим граф объединим соответствующие множества в СНМ рёбра, записанные в этой вершине. При выходе из вершины нужно откатить Откатывание состояния СНМ к состоянию, которое было при входе (об этом описано ниже). Когда мы добираемся до листа, в СНМ уже добавлены все рёбра, которые существуют во время выполнения соответствующего запроса, и только они. Поэтому если этот лист соответствует запросу третьего типа, его следует выполнить и сохранить ответ.

Как Для того, чтобы иметь возможность откатывать состояние СНМ? Каждый раз, когда мы изменяем что-то нужно при каждом изменении любого значения в СНМ, будем записывать в специальный массив, что именно мы изменили изменилось и какое было предыдущее значение. Это можно реализовать как массив пар (указатель, значение).

Каждое из <tex>O(m)</tex> рёбер записывается в <tex>O(\log m)</tex> вершин дерева отрезков. Поэтому операций <tex>\mathrm{union}</tex> в СНМ будет <tex>O(m \log m)</tex>. Каждая выполняется за <tex>O(\log n)</tex> (СНМ с ранговой эвристикой). Откаты не влияют на время работы.

Можно считать, что <tex>n = O(\log m)</tex>, так как в запросах используется не более <tex>2m</tex> вершин.

Время работы: <tex>O(m \log m \log n) = O(m \log^2 m)</tex>.