Персистентные деревья отрезков

Введение

Структуры данных можно разделить на две группы: эфемерные (ephemeral) и персистентные (persistent).

Эфемерными называются структуры данных, хранящие только последнюю свою версию.
Персистентные структуры, то есть те, которые сохраняют все свои предыдущие версии, в свою очередь можно разделить еще на две подгруппы: если структура данных, позволяет изменять только последнюю версию, она называется частично персистентной (partially persistent), если же позволяется изменять любую версию, такая структура считается полностью персистентной (fully persistent).

Далее будет рассмотрено дерево отрезков и его полностью персистентная версия.
Весь код доступен на GitHub.

Дерево отрезков

Те, кто уже знаком с деревьями отрезков, могут сразу перейти к разделу о персистентной версии.

Деревом отрезков называется структура данных, позволяющая для данного массива A быстро выполнять следующие операции:

• Change(i, x) — изменить значение A[i] на x
• F(i, j) — посчитать f(A[i], A[i + 1], ..., A[j])

Обе операции выполняются за O(log n). В качестве функции f часто берут сумму, минимум или максимум.

Описание

Пусть n — длина массива A, будем заполнять его нейтральными элементами до тех пор, пока его длина не станет равна степени двойки (например, если f — сумма, массив будет дополняться нулями).

Теперь построим такое двоичное дерево, что его листьями будут все элементы A и глубина всех листьев одинакова, а во всех остальных вершинах будут храниться значения f от значений дочерних вершин.

Рассмотрим в качестве примера дерево отрезков для массива A = [4, 1, 4, 2, 5, 3]:

Хранить такое дерево удобно как и двоичную кучу: в виде массива вершин, записанных подряд сверху вниз слева направо:

19  11 8  5 6 8 0  4 1 4 2 5 3 0 0

В таком случае для вершины с индексом i ее предком будет вершина ((i - 1) / 2), а левый и правый дочерние вершины будут иметь индексы (2 * i + 1) и (2 * i + 2) соответственно (считая, что элементы в массиве нумеруются с нуля).

Построение

Удобно строить дерево отрезков рекурсивно сверху вниз: для каждой вершины построить левую и правую дочерние вершины, после чего посчитать значение f от их значений, а для листов же просто записать соответствующее значение массива в дерево.

Строя дерево таким образом каждая вершина будет посещена один раз, и, так как количество вершин в дереве Θ(n), сложность построения также Θ(n).

Изменение

После того, как было изменено значение какого-либо элемента, в дереве могли испортиться некоторые из значений предков данного элемента. Исправить это можно, пересчитав значения предков данного элемента, поднимаясь по дереву снизу вверх.

Например, если в массиве A заменить A[3] на 10, то будут пересчитаны вершины со значениями 6, 11 и 19.

Так как высота дерева log n, то операция изменения затронет ровно log n вершин, значит, асимптотика операции O(log n).

Вычисление F

Данная операция будет выполняться рекурсивно сверху вниз.

Пусть в произвольной вершине v посчитано F для диапазона l..r, тогда нетрудно проверить, что в левой дочерней вершине посчитано значение F для l..((l + r) / 2), а в правой — для ((l + r) / 2 + 1)..r.

Предположим, что поступил запрос F(i, j), и текущая вершина — v. Возможны два случая:

• В узле v уже посчитано значение F(i, j). Тогда ответом на полученный запрос будет значение вершины v.
• В узле v записано F для большего диапазона. В таком случае рекурсивно вызовем вычисление F(i, (l + r) / 2) для левого дочерней вершины и F((l + r) / 2 + 1, j) для правой, и ответом будет f от этих двух значений.

Пример

Реализация дерева отрезков на C++.

Персистентное дерево отрезков

Добиться персистентности можно разными способами, самый простой из них — при каждом изменении делать полную копию старой версии и изменять ее, как обычное дерево отрезков, однако такой способ слишком затратен по памяти и ухудшает асимптотику операции Change до O(n).

Построение

Построение персистентного дерева отрезков будет аналогично построению обычного дерева отрезков за исключением того, что теперь для каждой вершины дополнительно придется в явном виде хранить ссылки на дочерние вершины.
Также дополнительно понадобится хранить массив вершин, являющихся корнями в соответствующих версиях дерева. При построении в него добавляется единственная вершина, являющаяся корнем полученного дерева.

Так как единственное изменение по сравнению с эфемерным деревом отрезков — это добавление информации о левой и правой дочерних вершинах, сложность построения осталось неизменной, то есть Θ(n).

Изменение

Вместо полного копирования дерева при изменении вершины к нему будут добавлены только те вершины, которые должны были измениться, и вместо изменения значений старых вершин, пересчитанные значения будут сохранены в новые. Все новые вершины будут ссылаться на одну вершину из дерева старой версии и на одну из только что добавленных.

Добавление новой ветки делается аналогично построению всего дерева за исключением того, что вместо построения двух дочерних вершин, новая вершина строится только в том направлении, в котором лежит измененная вершина.
После этого обновляется массив корневых вершин.

Так как при изменении только добавляется log n вершин, асимптотика операции — O(log n).

Вычисление F

Вычисление F производится аналогично эфемерному дереву. Единственные отличия: переходы к дочерним вершинам и запуск из разных корневых вершин.
Отсюда следует сложность O(log n).

Пример

Реализация персистентного дерева отрезков на C++.

Задачи

При помощи персистентного дерева отрезков можно решить задачу "Откат" (разбор задачи). Решение задачи с использованием приведенной выше реализации персистентного дерева отрезков доступно на GitHub.
Также здесь можно прочитать обсуждение задачи о k-ой порядковой статистике на диапазоне.

Автор: nagato