Структура данных дерево отрезков и её применение в задачах. Дерево отрезков

Структура данных дерево отрезков и её применение в задачах. Дерево отрезков

1. Постановка задачи

Рассмотрим следующую задачу. Дано $n$ ящиков, пронумерованных числами от $1$ до $n$, в каждом из которых лежит несколько шариков. Известно, что $n$ достаточно велико. Нам нужно уметь быстро выполнять следующие операции:

1. $add(c, w)$ - изменить количество шариков в ящике $c$, прибавив к нему $w$ шариков ($w$ может быть отрицательным);
2. $sum(a, b)$ - посчитать количество шариков в нескольких ящиках, расположенных по порядку с номерами от $a$ до $b$, то есть на отрезке $$.

Мы можем просто завести массив, в котором будем хранить число шариков в ящиках. Почему эта идея может оказаться неоптимальной? При изменении числа шариков в ящике мы меняем значение элемента массива с номером $c$, что выполняется за $O(1)$. Но чтобы посчитать сумму в нескольких идущих подряд ящиках, нам нужно будет сложить $b - a + 1$ чисел. Поскольку длина отрезка может быть почти $n$, то выполняется порядка $n$ сложений, то есть операция ${\it sum}$ выполняется за $O(n)$. При достаточно большом числе запросов суммы на отрезке решение задачи перебором является далеко не лучшим.

2. Корневая оптимизация

Первая идея, которая обычно приходит в голову, это разделить $n$ ящиков на $x$ групп таким образом, что первые несколько ящиков по порядку попадают в первую группу, следующие - во вторую, и так далее. Далее заведем дополнительный массив из $x$ элементов, где будет храниться количество шариков в каждой группе. Тогда при выполнении операции ${\it add}$ нам нужно будет выполнить два действия: изменить значение в соответствующей группе и в самом элементе. Зато операция ${\it sum}$ потребует меньших затрат: нужно сложить элементы группы, которой принадлежит число $a$ (обозначим ее $A$), начиная с элемента с номером $a$ и кончая последним, элементы группы, которой принадлежит число $b$ (обозначим ее $B$), начиная с первого и кончая элементом с номером $b$, что требует временных затрат порядка $O(\frac{n}{x})$ и прибавить к ним суммы элементов в группах, начиная с группы, следующей за $A$ и заканчивая группой, расположенной перед группой $B$, что требует временных затрат порядка $O(x)$. Всего нужно выполнить примерно $\frac{n}{x} + x$ операций. Если мы подберем число $x$ оптимальным образом, то эта идея называется корневой оптимизацией. Чтобы ответить на вопрос, какое $x$ является наилучшим, нужно устремить к минимуму выражение $\frac{n}{x} + x$. Возьмем от него производную по $x$ и приравняем ее к нулю: $-\frac{n}{x^{2}}+1=0$. Отсюда получаем $x=\sqrt{n}$. Таким образом, оптимальное количество групп, на которые нужно разбить ящики: $$. Мы добились оценки времени выполнения операции ${\it sum}$ $O(\sqrt{n})$, правда, увеличился расход по памяти, но всего лищь на $\sqrt{n}$ - число дополнительных ящиков для хранения сумм элементов в группах.

Дерево отрезков на указателях. Полное двоичное дерево

Полное двоичное дерево — это дерево, у каждого элемента которого есть ровно два дочерних элемента.Для работы с полным двоичным деревом можно и нужно использовать такую структуру данных, как массив. Нумеровать этот массив удобно с единицы . Пронумеруем каждый элемент двоичного дерева натуральными числами от 1 до 2ⁿ-1:Вся красота подхода в том, что очень легко вычислять номер детей и родителей.Формула вычисления «левого ребёнка»: i*2 , «правого»: i*2+1 .Например, вычислим номера детей у пятого элемента:

1. 5 х 2 = 10 ;
2. 5 х 2 + 1 = 11 .

А как от «ребёнка» подняться к «родителю»? Используем целочисленное деление i / 2 Ок, а как определить, левый ребёнок или правый? Ответ следующий: у левых детей чётные номера, у правых — нечётные .Запомним эти моменты.Возвратившись к нашему примеру бинарного дерева, зададимся вопросом, как нам его построить? Смотрите, у нас вначале есть массив чисел:Для него нужно построить двоичное дерево. Сколько потребуется памяти для хранения двоичного дерева, внизу которого находятся эти элементы?Ответ на этот вопрос — 2n , если n является степенью двойки.Идём дальше, ведь перед нами возникают ещё два вопроса:

1. с какого элемента необходимо разместить исходные числа в массиве полного двоичного дерева?
2. с какого элемента и в какую сторону мы начнём заполнять наше дерево предварительно рассчитанными суммами?

Ответить на первый вопрос достаточно просто: у нас 8 элементов, всего в массиве будет 16 элементов, значит, первый элемент будет под номером 16 — 8 = 8. И начинать строить мы будем слева-направо и снизу-вверх, начиная с 7 элемента, складывая значения у детей, вот так:Далее необходимо определить, как именно находить сумму нужного отрезка. Вернёмся к нашему первому примеру, пронумеруем элементы и зададим отрезок, причём обозначим первый элемент в отрезке, который нужно сложить, буквой L, а последний — R:Теперь необходимо ввести ещё одно понятие, чтобы был ясен алгоритм действий. Речь идёт о понятии фундаментальных элементов и соответствующих им фундаментальных отрезков. Фундаментальный элемент — это какой угодно элемент из всего массива, и ему соответствует фундаментальный отрезок, то есть те элементы из начального массива, которые являются его непосредственными детьми/внуками. Для фундаментального элемента с номером 4 “5” фундаментальный отрезок будет с 8 по 9 элемент: :Что касается фундаментального элемента с номером 10 — “7” (мы обозначили его L), он совпадает со своим фундаментальным отрезком. Можно ли расширить этот фундаментальный отрезок, не выходя за пределы L-R? В нашем случае можно. Правило для левой границы такое: если это левый ребёнок, то фундаментальный отрезок можно расширить, новый фундаментальный элемент будет являться родителем текущего. То есть мы можем в программе писать следующее:Теперь перейдём к правому элементу R. Он является фундаментальным элементом и левым ребёнком, поэтому расширить область мы уже не можем (выйдем за пределы отрезка). Значит, можем добавить этот элемент к ответу:Далее нужно, чтобы левый элемент двигался к правому, а правый — к левому. Для левого элемента с индексом L = 10 следующий индекс равен 5, т. к. он пойдёт к родителю. Но пойдёт сначала вправо, а потом вверх:Итак, значение L перешло на уровень выше и немного правее. Как же будет уменьшаться R? С помощью формулы (R – 1) / 2.Вот такой алгоритм. Что касается следующих значений переменных L и R, то далее они будут перемещаться следующим образом:Если же в дереве будет не 8 элементов, а неудобное число, скажем 12, нам придётся дополнить дерево (двоичное дерево должно быть полным) до 16-ти.Формула для вычисления количества элементов (берётся целая часть логарифма):Теперь вычислим ассоциативную функцию нахождения минимума . Вот наше дерево и отрезок:Как думаете, сколько раз в нашей функции будет задействован элемент № 5 — один или два? Разумеется, один, но каким образом это проверяется в алгоритме? На самом деле, этот элемент является либо левым, либо правым сыном, а значит, выполнится действие либо для L, либо для R.+Теперь рассмотрим операцию изменения. Допустим, изменился какой-нибудь элемент, например, вместо 7 пришёл 0. Чтобы наше дерево отрезков осталось в рабочем состоянии, необходимо обновить всех родителей, причём нужно идти до самого верха.

Дерево отрезков с++. Дерево отрезков

Метки нет()

Добрый день, помогите пож-та решить задачи на с++. Нашел решение (расписаны все алгоритмы, процедуры подсчета и т. д.), но сложность состоит в том, что я не понимаю строищихся структур и вообще никогда не программировал на c++.Поэтому прошу помочь собрать все воедино (чтение из файла, работа программы, запись в файл). Основная задача - считать с файла, воспользоваться функцией, вывести в фай лДан массив целых чисел. Поступают запросы модификации элемента и поиска суммы элементов на отрезке. Необходимо ответить на каждый запрос суммы.Вход:В первой строке через пробел записаны два натуральных числа N и M (N, M . Онбудет содержать сумму элементов A, т.е. всего массива. Левый сын корня будет храниться в элементе T и содержать сумму первой половины массива A: A, а правый сын - в элементе T и содержать сумму элементов A. В общем случае, если T -ый элемент содержит сумму элементов с L-го по R-ый, то его левым сыном будет элемент T и содержать сумму A, а его правым сыном будет T и содержать сумму A. Исключение, разумеется, составляют листья дерева - вершины, в которых L = R.Рассмотрим теперь операцию суммы на некотором отрезке . Мы встаём в корень дерева (i=1), ирекурсивно движемся вниз по этому дереву. Если в какой-то момент оказывается, что L и R совпадают с границами отрезка текущего элемента, то мы просто возвращаем значение текущего элемента T. Иначе, если отрезок целиком попадает в отрезок левого или правого сына текущего элемента, то мы рекурсивно вызываем себя из этого сына и найденное значение возвращаем. Наконец, если отрезок частично принадлежит и отрезку левого сына, и отрезку правого сына, то делим отрезок на два отрезка и так, чтобы первый отрезок целиком принадлежал отрезку левого сына, а второй отрезок - отрезку правого сына, и рекурсивно вызываем себя и от первого, и от второго отрезков, возвращая сумму найденных сумм.Теперь рассмотрим операцию изменения значения некоторого элемента с индексом K. Будем спускаться по дереву от корня, ища тот лист, который содержит значение элемента A. Когда мы найдём этот элемент, просто изменим соответствующее значение в массиве T и будем подниматься от текущего элемента обратно к корню, пересчитывая текущие значения T. Понятно, что таким образом мы изменим все значения в дереве, которые нужно изменить.

Дерево отрезков алгоритмика. Ок, как это нам поможет?

Опишем, как с помощью такой структуры решить исходную задачу.

Запрос обновления . Нам нужно обновить значения в вершинах таким образом, чтобы они соответствовали новому значению $a = x$.

Изменим все вершины, в суммах которых участвует $k$-тый элемент. Их будет $\Theta(\log n)$ — по одной с каждого уровня.

Это можно реализовать как рекурсивную функцию: ей передаётся текущая вершина дерева отрезков, и функция выполняет рекурсивный вызов от одного из двух своих сыновей (от того, который содержит $k$-ый элемент в своём отрезке), а после этого — пересчитывает значение суммы в текущей вершине точно таким же образом, как мы это делали при построении дерева отрезков.

Запрос суммы . Мы знаем, что во всех вершинах лежат корректные значения, и нам с помощью них посчитать сумму на отрезке.

Сделаем тоже рекурсивную функцию, рассмотрев три случая:

1. Если отрезок вершины лежит целиком в отрезке запроса, то вернуть записанную в ней сумму.
2. Если отрезки вершины и запроса не пересекаются, то вернуть 0.
3. Иначе разделиться рекурсивно на 2 половины и вернуть сумму этой функции от обоих детей.

Чтобы разобраться, почему это работает за $O(\log n)$, нужно оценить количество «интересных» отрезков — тех, которые порождают новые вызовы рекурсии. Это будут только те, которые содержат границу запросов — остальные сразу завершатся. Обе границы отрезка содержатся в $O(\log n)$ отрезках, а значит и итоговая асимптотика будет такая же.

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

Далее этой главе мы рассмотрим разные реализации и варианты этой структуры и их применения.

Дерево отрезков снизу. Дерево отрезков. Построение

Дерево отрезков (англ. Segment tree ) — это структура данных, которая позволяет за асимптотику $O(\backslash log\; n)$ реализовать любые операции, определяемые на множестве, на котором данная операция ассоциативна, и существует нейтральный элемент относительно этой операции, то есть на моноиде . Например, суммирование на множестве натуральных чисел, поиск минимума на любом числовом множестве, перемножение матриц на множестве матриц размера $N*N$ , объединение множеств, поиск наибольшего общего делителя на множестве целых чисел и многочленов.

При этом дополнительно возможно изменение элементов массива: как изменение значения одного элемента, так и изменение элементов на целом подотрезке массива , например разрешается присвоить всем элементам $a$ какое-либо значение, либо прибавить ко всем элементам массива какое-либо число. Структура занимает $O(n)$ памяти, а ее построение требует $O(n)$ времени.

Структура

Структура представляет собой дерево, листьями которого являются элементы исходного массива. Другие вершины этого дерева имеют по $2$ ребенка и содержат результат операции от своих детей (например минимум или сумму). Таким образом, корень содержит результат искомой функции от всего массива $$ , левый ребёнок корня содержит результат функции на $$ , а правый, соответственно результат на $$ . И так далее, продвигаясь вглубь дерева.

Построение дерева

Пусть исходный массив $a$ состоит из $n$ элементов. Для удобства построения увеличим длину массива $a$ так, чтобы она равнялась ближайшей степени двойки, т.е. $2^k$ , где $2^k\; \backslash geqslant\; n$ . Это сделано, для того чтобы не допустить обращение к несуществующим элементам массива при дальнейшем процессе построения. Пустые элементы необходимо заполнить нейтральными элементами моноида. Тогда для хранения дерева отрезков понадобится массив $t$ из $2^\{k+1\}$ элементов, поскольку в худшем случае количество вершин в дереве можно оценить суммой $n+\backslash dfrac\{n\}\{2\}+\backslash dfrac\{n\}\{4\}\; \backslash ldots\; +1\; \backslash lt\; 2n$ , где $n=2^k$ . Таким образом, структура занимает линейную память.

Процесс построения дерева заключается в заполнении массива $t$ . Заполним этот массив таким образом, чтобы $i$ -й элемент являлся бы результатом некоторой бинарной операции (для каждой конкретной задачи своей) от элементов c номерами $2i+1$ и $2i+2$ , то есть родитель являлся результатом бинарной операции от своих сыновей (обозначим в коде эту операцию как " $\backslash circ$ "). Один из вариантов — делать рекурсивно. Пусть у нас имеются исходный массив $a$ , а также переменные $\backslash mathtt\{tl\}$ и $\backslash mathtt\{tr\}$ , обозначающие границы текущего полуинтервала. Запускаем процедуру построения от корня дерева отрезков ( $i=0$ , $\backslash mathtt\{tl\}=0$ , $\backslash mathtt\{tr\}=n$ ), а сама процедура построения, если её вызвали не от листа, вызывает себя от каждого из двух сыновей и суммирует вычисленные значения, а если её вызвали от листа — то просто записывает в себя значение этого элемента массива (Для этого у нас есть исходный массив $a$ ). Асимптотика построения дерева отрезков составит, таким образом, $O(n)$ .

Выделяют два основных способа построения дерева отрезков: построение снизу и построение сверху. При построении снизу алгоритм поднимается от листьев к корню (Просто начинаем заполнять элементы массива $t$ от большего индекса к меньшему, таким образом при заполнении элемента $i$ его дети $2i+1$ и $2i+2$ уже будут заполнены, и мы с легкостью посчитаем бинарную операцию от них), а при построении сверху спускается от корня к листьям. Особенные изменения появляются в реализации запросов к таким деревьям отрезков.

Массовые операции дерево отрезков. Дерево отрезков для поиска суммы

Одна из простейших функций, которую можно считать за \(O(\log N)\) с помощью дерева отрезков - сумма.

При построении дерева в каждой его вершине сохраним сумму на соответствующем отрезке (построение будет вестись рекурсивно, поэтому достаточно просто сложить суммы на двух дочерних отрезках). Затем каждый запрос суммы на отрезке будем разбивать на \(2 \log N\) отрезков, и находить сумму на каждом из них за \(O(1)\), используя предпросчитанные значения. Таким образом сложность запроса суммы равна \(O(\log N)\).

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

Для реализации запроса суммы и запроса модификации обход дерева реализуется с помощью одного и того же алгоритма, основанного на DFS. Пусть границы нашего запроса \(\) (в случае запроса модификации \(L = R\)), а границы отрезка, соответствующего текущей вершине \(\). В зависимости от взаимного положения этих границ, существуют три варианта действий алгоритма:

Текущий отрезок полностью входит в запрос (\(L \le TL; TR \le R\)).

Если это запрос суммы, вернём предпросчитанную сумму на отрезке. Если это запрос модификации, изменим элемент и пересчитаем сумму. В дочерние вершины спускаться нет надобности.

Текущий отрезок полностью не входит в запрос (\(TR

Никаких действий выполнять не нужно, просто выйдем из функции. Если это запрос суммы, просто вернём \(0\).

Текущий отрезок частично входит в запрос.

Вызовем функцию рекурсивно для двух дочерних отрезков. Если это запрос суммы, вернём сумму двух полученных значений. Если это запрос модификации, пересчитаем значение суммы для текущего отрезка (так как оно могло измениться).

Персистентное дерево отрезков. Метод копирование пути

Пусть есть сбалансированное дерево поиска . Все операции в нем делаются за $O(h)$ , где $h$ — высота дерева, а высота дерева $O$$(\backslash log\; n)$ , где $n$ — количество вершин. Пусть необходимо сделать какое-то обновление в этом сбалансированном дереве, например, добавить очередной элемент, но при этом нужно не потерять старое дерево. Возьмем узел, в который нужно добавить нового ребенка. Вместо того чтобы добавлять нового ребенка, скопируем этот узел, к копии добавим нового ребенка, также скопируем все узлы вплоть до корня, из которых достижим первый скопированный узел вместе со всеми указателями. Все вершины, из которых измененный узел не достижим, мы не трогаем. Количество новых узлов всегда будет порядка логарифма. В результате имеем доступ к обеим версиям дерева.

Так как рассматривается сбалансированное дерево поиска, то поднимая вершину вверх при балансировке, нужно делать копии всех вершин, участвующих во вращениях, у которых изменились ссылки на детей. Таких всегда не более трех, поэтому ассимптотика $O$$(\; \backslash log\; n)$ не пострадает. Когда балансировка закончится, нужно дойти вверх до корня, делая копии вершин на пути.

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

Реализация на основе дерева отрезков

На основе дерева отрезков можно построить полностью персистентную структуру данных.

Для реализации персистентного дерева отрезков удобно несколько изменить структуру дерева. Для этого будем использовать явные указатели $L$ и $R$ для дочерних элементов. Кроме того, заведем массив $roots$ , в котором $roots$ указывает на корень дерева отрезков версии $i$

Для построения персистентного дерева отрезков из $n$ элементов необходимо применить $n$ раз операцию добавления элемента к последней версии дерева. Для того, чтобы добавить новый элемент к $k$ -ой версии дерева, необходимо проверить, является ли оно полным бинарным. Если да, то создадим новый корень, левым сыном сделаем $roots$ . Иначе, сделаем копию корня исходной версии. Добавим корень в конец массива корней. Далее, спускаясь от корня к первому свободному листу, будем создавать несуществующие узлы и клонировать существующие. После этого в новой ветке необходимо обновить значение функции и некоторые указатели дочерних элементов. Поэтому, возвращаясь из рекурсии, будем менять один указатель на только что созданную или скопированную вершину, а также обновим значение функции, для которой строилось дерево. После этой операции в дереве появится новая версия, содержащая вставленный элемент.

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

Здесь изображено персистентное дерево отрезков с операцией минимум, в котором изначально было 3 вершины. Сперва к нему была добавлена вершина со значением 2, а потом изменена вершина со значением 7. Цвет ребер и вершин соответствует времени их появления. Синий цвет элементов означает, что они были изначально, зеленый - что они появились после добавления, а оранжевый - что они появились после изменения элемента.

Китайское дерево отрезков. Предыстория

Данная история мало конструктивна, нужна скорее для понимания того, откуда возникла идея для оптимизации. Подробно о самом алгоритме и написано ниже.

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

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

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

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

Очевидный вопрос, а даст ли нам этот подход какой-нибудь бонус?