23 January

Дерево отрезков: просто и быстро

OTUS. Онлайн-образование corporate blogAlgorithms
Накануне очередного запуска курса «Алгоритмы для разработчиков» мы провели открытый урок. На нём поговорили об известной идее дерева отрезков, обсудили, как его строить, обновлять и быстро O(log n) вычислять сумму чисел любого отрезка данного массива. Алгоритм очень простой и экономный: нужно O(n) памяти. Для закрепления материала решили олимпиадную задачу.




Вебинар провёл опытный программист и преподаватель, а также руководитель курса «Алгоритмы для разработчиков» Евгений Волосатов.

Присказка


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

К примеру, представьте, что надо найти сумму следующих чисел:



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



Что значит быстро? Это значит быстрее, чем, если бы мы просто суммировали числа. Ведь чисел может быть и миллионы, и миллиарды…

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

Возвратимся к нашему ряду:



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



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

Усложняем задачу:



Чтобы найти сумму этого отрезка, нам нужно сложить элементы, которые, так или иначе, покрывают наш отрезок:



Разумеется, 3 + 13 + 19 = 35. Обратите внимание, чтобы найти сумму семи чисел, мы сложили только три. Если бы отрезок состоял из тысячи элементов, достаточно было бы сложить в среднем 10 элементов, так как мы имеем логарифмическую сложность с логарифмом по основанию 2. И это быстро!

Полное двоичное дерево


Полное двоичное дерево — это дерево, у каждого элемента которого есть ровно два дочерних элемента.

Для работы с полным двоичным деревом можно и нужно использовать такую структуру данных, как массив. Нумеровать этот массив удобно с единицы. Пронумеруем каждый элемент двоичного дерева натуральными числами от 1 до 2n-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 элемент: [“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#:



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



На этом всё, если хотите подробностей, смотрите видео целиком. Также можете на досуге почитать следующие авторские статьи нашего преподавателя Евгения Волосатова на Хабре:

Балансировка красно-чёрных деревьев — Три случая;
Ход конём по битам. Шахматный Bitboard.
Tags: алгоритмы дерево отрезков
Hubs: OTUS. Онлайн-образование corporate blog Algorithms
+23
4.5k 77
Comments 6
Ads