Министерство образования и науки Российской Федерации
Министерство образования Саратовской области
Национальный исследовательский Саратовский государственный университет имени Н.Г. Чернышевского
Саратовский областной институт развития образования
Комитет по информатизации Саратовской области
Комитет по образованию администрации муниципального образования «Город Саратов»
Автономная некоммерческая организация «Информационные технологии в образовании»
Автономная некоммерческая организация «Научно-исследовательский центр «Образование. Качество. Отрасль»»
IX Всероссийская (с международным участием) научно-практическая конференция
«Информационные технологии в образовании»
«ИТО-Саратов-2017»
2-3 ноября 2017 года, г. Саратов

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

1 ФГБОУ ВПО "Саратовский государственный университет имени Н.Г. Чернышевского", 2 Федеральное государственное бюджетное образовательное учреждение высшего образования «Саратовский национальный исследовательский государственный университет имени Н.Г. Чернышевского»
Рассмотрена структура данных "Персистентное дерево отрезков", использующаяся в решении олимпиадных задач по программированию. Описана его структура и реализация на языке с++.

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

Демина Надежда Александровна, магистрант 2 курса, Прикладная математика и информатика  КНиИТ

Курылев Дмитрий Петрович, студент 6 курса, Компьютерная безопасность КНиИТ

Портенко Марина Сергеевна, старший преподаватель КНиИТ

 

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

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

1 Построение

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

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

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

2 Запросы обновление

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

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

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

3 Вычисление функции

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

4 Реализация

Рассмотрим некоторые детали реализации класса персистентого дерева отрезков PersistentSegmentTreeна С++.

Стоит отметить, данная реализации применима для получения значений на отрезках не для частной функции, а для любой ассоциативной функции. Следовательно, типы данных массива тоже могут быть произвольными и передаются пользователем через шаблон. [3]

            Теперь дерево хранится не через массив, а через указатели. То есть хранится узел, значение в нем и от него в чистом виде идут указатели на левого и правого потомков. Для этого представлена реализация структуры Node.

template<classT>

structNode{

            T item;

            Node *left;

            Node *right;

            Node(T x) : item(x){

                        left = NULL;

                        right = NULL;

            }

            Node() : item(NULL), left(NULL), right(NULL)

            {

            }

};

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

Далее рассмотрена структуру самого класса.

Приведем код полей класса с комментариями.

vector<Node<T> *>trees; // массив корней версий дерева

            intn; // количество элементов в исходном массиве

            T *a; // сам исходный массив

            F func;// функтор для функции, по которой строится дерево

Конструктор данного класса будет выглядеть следующим образом:

PersistentSegmentTree(T *mas, int n, F func)

            {

                        a = mas;

                        this->n = n;

                        this->func = func;

                        trees.push_back(build(0, n - 1));

            }

В него передается исходный массив, количество элементов в нем и функтор для функции.

В основном, методы класса, похожи на методы для работы с эфемерным деревом отрезков, поэтому не будем подробно останавливаться на них. Приведем лишь объявление схожих методов.

Private-методы: 

Node<T>* build(intl, intr);  // построение дерева

TgetResult(Node<T> *node, intl, intr, intL, intR, Tinit)  // получениерезультатаназапроснаотрезке

Public –методы:

void backUp(int cnt); //  откатверсийнаcnt

TgetResult(intl, intr, Tinit); // получение результата на запрос на отрезке

TgetResult(intl, intr, intnum, Tinit);  // получениерезультатадля версии numна запрос на отрезке

void update(int pos, int x); // обновление

Функция обновления для персистентного поменялась значительно в сравнении с функцией обновления для эфемерного дерева. Поэтому рассмотрим ее подробнее.

voidupdate(Node<T> *lastNode, Node<T> *newNode, intl, intr, intpos, intx){

                        if (l == r){

                                    newNode->item = x;

                                    return;

                        }

                        int mid = (l + r) / 2;

                        if (pos <= mid){

                                    newNode->left = new Node<T>();

                                    update(lastNode->left, newNode->left, l, mid, pos, x);

                                    newNode->right = lastNode->right;

                        }

                        else

                        {

                        newNode->right = new Node<T>();

                        update(lastNode->right, newNode->right, mid + 1, r, pos, x);

                                    newNode->left = lastNode->left;

                        }

newNode->item = func(newNode->left->item, newNode->right->item);

            }

            Как уже говорилось ранее, в данной функции мы не обновляем, а достраиваем изменяющуюся ветку дерева. Для этого в качестве параметров передается старый узел, новый узел, текущий отрезок и позиция обновления с новым значением. На каждом рекурсивном вызове одна из веток нового узла будет ссылаться на старого потомка, а другая будет изменяться, и таким образом, выстраивается заново.

             Как именно надо указывать функцию через функтор, и что это такое?

Функторы в C++ являются сокращением от «функциональные объекты». Функциональный объект является экземпляром класса С++, в котором определён operator(). Если для C++ класса определяется определите operator(), то получается объект, который действует как функция, но может также хранить состояние. [5]

Приведем пример функтора, описывающего вычисление функции минимума.

template<classT>

class Min

{

public:

            T operator()(T a, T b)

            {

                        return (a < b) ? a : b;

            }

};

Пример создания объекта класса PersistentSegmentTree   будет выглядеть так.

PersistentSegmentTree <int, Min<int>> tree = PersistentSegmentTree<int, Min<int>>(a, n, Min<int>());

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

Список использованных источников
  1. Персистентные деревья отрезков [Электронный ресурс] – URL: http://habrahabr.ru/post/125995 (дата обращения: 26.05.15). Загл. с экрана. Яз. рус.
  2. Функторы в языках программирования [Электронный ресурс] – URL: http://habrahabr.ru/post/125995/ (дата обращения: 26.05.15). Загл. с экрана. Яз. рус.
  3. Демина Н.А., Портенко М.С.. Использование дерева отрезков для нахождения значений ассоциативной функции на подмассиве. Информационные технологии в образовании: Материалы VII Всерос. научно-практ. конф. – Саратов: ООО «Издательский центр «Наука»», 2015. - С. 39-42. ISBN 978-5-9758-1610-8.
Вид представления доклада  Устное выступление и публикация
Ключевые слова  Дерево отрезков, Структуры данных, Алгоритмы, Олимпиадное программирование

В статусе «Черновик» Вы можете производить с тезисами любые действия.

В статусе «Отправлено в Оргкомитет» тезисы проходят проверку в Оргкомитете. Статус «Черновик» может быть возвращен тезисам либо если есть замечания рецензента, либо тезисы превышают требуемый объем, либо по запросу участника.

В статусе «Рекомендован к публикации» тезис публикуется на сайте. Статус «Черновик» может быть возвращен либо по запросу участника, либо при неоплате публикации, если она предусмотрена, либо если тезисы превышают требуемый объем.

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

Статус «Отклонен» означает, что по ряду причин, которые указаны в комментариях к тезису, Оргкомитет не может принять тезисы к публикации. Из отклоненных тезис в «Черновики» может вернуть только Председатель программного или председатель оргкомитета.