Дерево отрезков: просто и быстро
Накануне очередного запуска курса «Алгоритмы для разработчиков» мы провели открытый урок. На нём поговорили об известной идее дерева отрезков, обсудили, как его строить, обновлять и быстро O(log n) вычислять сумму чисел любого отрезка данного массива. Алгоритм очень простой и экономный: нужно O(n) памяти. Для закрепления материала решили олимпиадную задачу.
Вебинар провёл опытный программист и преподаватель, а также руководитель курса «Алгоритмы для разработчиков» Евгений Волосатов.
Присказка
Дерево отрезков — это структура данных, которая позволяет алгоритмически просто и логарифмически быстро находить сумму элементов массива на заданном отрезке.
К примеру, представьте, что надо найти сумму следующих чисел:
При этом нам нужно не просто вычислить сумму чисел указанной последовательности (сумму элементов определённого массива), а максимально быстро найти сумму любой последовательности из этих чисел. То есть мы можем задать какой-нибудь интервал (отрезок) и максимально быстро дать ответ, чему равна сумма чисел из этого интервала:
Что значит быстро? Это значит быстрее, чем, если бы мы просто суммировали числа. Ведь чисел может быть и миллионы, и миллиарды…
Именно желание быстро находить сумму последовательных элементов и стало мотивацией нашего вебинара. Причём, речь идёт не только о сумме, но и о других задачах, например, вычислении любой ассоциативной функции. Таким образом, мы говорим об операциях, выполнение которых не зависит от порядка вычисления.
Возвратимся к нашему ряду:
Очевидно, что если мы хотим находить результат быстро, нужно посчитать некоторые суммы заранее. Первое, что приходит на ум, складывать попарно:
Теперь, если нужно найти сумму чисел, мы можем сделать это практически моментально. Например, чтобы найти сумму упомянутого выше отрезка, достаточно будет 13 прибавить к 9. Всё элементарно: для нахождения суммы четырёх чисел мы сложили только два.
Чтобы найти сумму этого отрезка, нам нужно сложить элементы, которые, так или иначе, покрывают наш отрезок:
Разумеется, 3 + 13 + 19 = 35. Обратите внимание, чтобы найти сумму семи чисел, мы сложили только три. Если бы отрезок состоял из тысячи элементов, достаточно было бы сложить в среднем 10 элементов, так как мы имеем логарифмическую сложность с логарифмом по основанию 2. И это быстро!
Полное двоичное дерево
Полное двоичное дерево — это дерево, у каждого элемента которого есть ровно два дочерних элемента.
Для работы с полным двоичным деревом можно и нужно использовать такую структуру данных, как массив. Нумеровать этот массив удобно с единицы. Пронумеруем каждый элемент двоичного дерева натуральными числами от 1 до 2 n -1:
Вся красота подхода в том, что очень легко вычислять номер детей и родителей.
Формула вычисления «левого ребёнка»: i*2, «правого»: i*2+1.
Например, вычислим номера детей у пятого элемента:
А как от «ребёнка» подняться к «родителю»? Используем целочисленное деление i / 2
Ок, а как определить, левый ребёнок или правый? Ответ следующий: у левых детей чётные номера, у правых — нечётные.
Возвратившись к нашему примеру бинарного дерева, зададимся вопросом, как нам его построить? Смотрите, у нас вначале есть массив чисел:
Для него нужно построить двоичное дерево. Сколько потребуется памяти для хранения двоичного дерева, внизу которого находятся эти элементы?
Ответ на этот вопрос — 2n, если n является степенью двойки.
Идём дальше, ведь перед нами возникают ещё два вопроса:
- с какого элемента необходимо разместить исходные числа в массиве полного двоичного дерева?
- с какого элемента и в какую сторону мы начнём заполнять наше дерево предварительно рассчитанными суммами?
Ответить на первый вопрос достаточно просто: у нас 8 элементов, всего в массиве будет 16 элементов, значит, первый элемент будет под номером 16 — 8 = 8. И начинать строить мы будем слева-направо и снизу-вверх, начиная с 7 элемента, складывая значения у детей, вот так:
Далее необходимо определить, как именно находить сумму нужного отрезка. Вернёмся к нашему первому примеру, пронумеруем элементы и зададим отрезок, причём обозначим первый элемент в отрезке, который нужно сложить, буквой L, а последний — R:
Теперь необходимо ввести ещё одно понятие, чтобы был ясен алгоритм действий. Речь идёт о понятии фундаментальных элементов и соответствующих им фундаментальных отрезков. Фундаментальный элемент — это какой угодно элемент из всего массива, и ему соответствует фундаментальный отрезок, то есть те элементы из начального массива, которые являются его непосредственными детьми/внуками. Для фундаментального элемента с номером 4 “5” фундаментальный отрезок будет с 8 по 9 элемент: [“2”; “3”]:
Что касается фундаментального элемента с номером 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#:
Отправляем на проверку, видим, что решение принято и является полным, а значит, наш алгоритм работает.
На этом всё, если хотите подробностей, смотрите видео целиком. Также можете на досуге почитать следующие авторские статьи нашего преподавателя Евгения Волосатова на Хабре:
Источник
Дерево отрезков. Построение
Дерево отрезков (англ. Segment tree) — это структура данных, которая позволяет за асимптотику [math]O(\log n)[/math] реализовать любые операции, определяемые на множестве, на котором данная операция ассоциативна, и существует нейтральный элемент относительно этой операции, то есть на моноиде. Например, суммирование на множестве натуральных чисел, поиск минимума на любом числовом множестве, перемножение матриц на множестве матриц размера [math]N*N[/math] , объединение множеств, поиск наибольшего общего делителя на множестве целых чисел и многочленов.
При этом дополнительно возможно изменение элементов массива: как изменение значения одного элемента, так и изменение элементов на целом подотрезке массива, например разрешается присвоить всем элементам [math]a[l \ldots r][/math] какое-либо значение, либо прибавить ко всем элементам массива какое-либо число. Структура занимает [math]O(n)[/math] памяти, а ее построение требует [math]O(n)[/math] времени.
Структура
Структура представляет собой дерево, листьями которого являются элементы исходного массива. Другие вершины этого дерева имеют по [math]2[/math] ребенка и содержат результат операции от своих детей (например минимум или сумму). Таким образом, корень содержит результат искомой функции от всего массива [math][0\ldots n-1][/math] , левый ребёнок корня содержит результат функции на [math][0\ldots\dfrac][/math] , а правый, соответственно результат на [math][\dfrac+1\ldots n-1][/math] . И так далее, продвигаясь вглубь дерева.
Построение дерева
Пусть исходный массив [math]a[/math] состоит из [math]n[/math] элементов. Для удобства построения увеличим длину массива [math]a[/math] так, чтобы она равнялась ближайшей степени двойки, т.е. [math]2^k[/math] , где [math]2^k \geqslant n[/math] . Это сделано, для того чтобы не допустить обращение к несуществующим элементам массива при дальнейшем процессе построения. Пустые элементы необходимо заполнить нейтральными элементами моноида. Тогда для хранения дерева отрезков понадобится массив [math]t[/math] из [math]2^[/math] элементов, поскольку в худшем случае количество вершин в дереве можно оценить суммой [math]n+\dfrac+\dfrac \ldots +1 \lt 2n[/math] , где [math]n=2^k[/math] . Таким образом, структура занимает линейную память.
Выделяют два основных способа построения дерева отрезков: построение снизу и построение сверху. При построении снизу алгоритм поднимается от листьев к корню (Просто начинаем заполнять элементы массива [math]t[/math] от большего индекса к меньшему, таким образом при заполнении элемента [math] i [/math] его дети [math]2i+1[/math] и [math]2i+2[/math] уже будут заполнены, и мы с легкостью посчитаем бинарную операцию от них), а при построении сверху спускается от корня к листьям. Особенные изменения появляются в реализации запросов к таким деревьям отрезков.
Реализация построения сверху:
function treeBuild(T a[], int i, int tl, int tr): // мы находимся в вершине с номером i, который отвечает за полуинтервал [tl, tr) if tr - tl == 1 t[i] = a[tl] else tm = (tl + tr) / 2 // середина отрезка treeBuild(a, 2 * i + 1, tl, tm) treeBuild(a, 2 * i + 2, tm, tr) t[i] = t[2 * i + 1] t[2 * i + 2] Реализация построения снизу:
function treeBuild(T a[]): for i = 0 to n - 1 t[n - 1 + i] = a[i] for i = n - 2 downto 0 t[i] = t[2 * i + 1] t[2 * i + 2] См. также
Источники информации
Источник