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

Автор: admin от 24-04-2012, 21:51, посмотрело: 3 779

Введение


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

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

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

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


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

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


  • Change(i, x) — изменить значение A на x

  • F(i, j) — посчитать f(A, 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++.

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

Задачи


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



Источник: Android

Категория: Операционные системы / Android

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

Добавление комментария

Имя:*
E-Mail:
Комментарий:
  • bowtiesmilelaughingblushsmileyrelaxedsmirk
    heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
    winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
    worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
    expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
    disappointedconfoundedfearfulcold_sweatperseverecrysob
    joyastonishedscreamtired_faceangryragetriumph
    sleepyyummasksunglassesdizzy_faceimpsmiling_imp
    neutral_faceno_mouthinnocent