9. Динамическое дерево отрезков Персистентные структуры данных
Дерево отрезков — структура данных, которая может быть преобразована в персистентную (сохраняет предыдущие состояния при каждой модификации). Это позволяет: обращаться к любой версии дерева и выполнять запросы на ней; сохранять исходную цепь модификаций, а от старой версии структуры ответвляется новая. Структура: дерево отрезков — полное бинарное дерево, в котором каждая вершина отвечает за некоторый отрезок в массиве. Корень дерева отвечает за весь массив, его две дочерние вершины — за две половины, и так далее. У каждой вершины, отвечающей за отрезок длиной больше 1, есть две дочерние вершины, отвечающие за левую и правую половины этого отрезка. Листья дерева отрезков отвечают за отдельные элементы (отрезки длиной 1). Принцип работы Построение персистентного дерева отрезков аналогично построению обычного дерева отрезков, но для каждой вершины дополнительно хранятся ссылки на дочерние вершины. Также дополнительно хранится массив вершин, являющихся корнями в соответствующих версиях дерева. При построении в него добавляется единственная вершина — корень полученного дерева. Изменение: Вместо полного копирования дерева при изменении вершины к нему добавляются только те вершины, которые должны были измениться. Вместо изменения значений старых вершин пересчитанные значения сохраняются в новые. Важно: не используется подход, при котором при каждом изменении делается полная копия старой версии и изменяется она, как обычное дерево отрезков, — такой способ слишком затратен по памяти и ухудшает асимптотику операции изменения до O(n). Реализация Существует несколько способов сделать структуру персистентной: Полное копирование — при любом изменении делается полная копия прошлого состояния структуры, и указатель на неё оставляется в таблице версий. Указатель на текущее состояние передвигается на новую версию. Копирование пути — дублируются только родительские узлы, что позволяет сэкономить память, но часть не модифицированных компонентов всё равно дублируется. Метод «толстых» узлов — сводит издержки памяти к минимуму, но применим не ко всем структурам данных, а лишь к тем, которые можно представить в виде «машины указателей». Сложность Асимптотика операций в персистентном дереве отрезков не меняется по сравнению с обычным деревом отрезков, но общее потребление памяти увеличивается. Например: Построение — Θ(n). Изменение — O(log n) — так как высота дерева — log n, то операция изменения затронет ровно log n вершин.
Дерево отрезков — структура данных, которая может быть преобразована в персистентную (сохраняет предыдущие состояния при каждой модификации). Это позволяет: обращаться к любой версии дерева и выполнять запросы на ней; сохранять исходную цепь модификаций, а от старой версии структуры ответвляется новая. Структура: дерево отрезков — полное бинарное дерево, в котором каждая вершина отвечает за некоторый отрезок в массиве. Корень дерева отвечает за весь массив, его две дочерние вершины — за две половины, и так далее. У каждой вершины, отвечающей за отрезок длиной больше 1, есть две дочерние вершины, отвечающие за левую и правую половины этого отрезка. Листья дерева отрезков отвечают за отдельные элементы (отрезки длиной 1). Принцип работы Построение персистентного дерева отрезков аналогично построению обычного дерева отрезков, но для каждой вершины дополнительно хранятся ссылки на дочерние вершины. Также дополнительно хранится массив вершин, являющихся корнями в соответствующих версиях дерева. При построении в него добавляется единственная вершина — корень полученного дерева. Изменение: Вместо полного копирования дерева при изменении вершины к нему добавляются только те вершины, которые должны были измениться. Вместо изменения значений старых вершин пересчитанные значения сохраняются в новые. Важно: не используется подход, при котором при каждом изменении делается полная копия старой версии и изменяется она, как обычное дерево отрезков, — такой способ слишком затратен по памяти и ухудшает асимптотику операции изменения до O(n). Реализация Существует несколько способов сделать структуру персистентной: Полное копирование — при любом изменении делается полная копия прошлого состояния структуры, и указатель на неё оставляется в таблице версий. Указатель на текущее состояние передвигается на новую версию. Копирование пути — дублируются только родительские узлы, что позволяет сэкономить память, но часть не модифицированных компонентов всё равно дублируется. Метод «толстых» узлов — сводит издержки памяти к минимуму, но применим не ко всем структурам данных, а лишь к тем, которые можно представить в виде «машины указателей». Сложность Асимптотика операций в персистентном дереве отрезков не меняется по сравнению с обычным деревом отрезков, но общее потребление памяти увеличивается. Например: Построение — Θ(n). Изменение — O(log n) — так как высота дерева — log n, то операция изменения затронет ровно log n вершин.