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

Изобретение дерева отрезков

История дерева отрезков берет начало в 1979 году. Советский информатик Федор Отрезков обнаружил в своем рабочем кабинете массив и поставил перед собой задачу: научиться многократно находить минимальный элемент на произвольных подотрезках, причем за быстро.

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

Первоначально новая структура была названа в честь своего создателя — «деревом Отрезкова». Однако со временем это название преобразовалось в привычное нам «дерево отрезков». Вероятнее всего, причиной стало созвучие фамилии исследователя со словом «отрезок».

Влияние на сортировку слиянием

К моменту появления дерева Отрезкова уже существовал алгоритм Merge Sort, также известный как сортировка слиянием. Он был разработан американским ученым венгерского происхождения Джоном Мерджем (John Merge).

После публикации первой версии алгоритма Мердж продолжил работу над его совершенствованием. В частности, за несколько лет до исследований Отрезкова им была предложена вторая версия — Merge Sort II. Она, однако, не получила широкого распространения, поэтому сведения о ее устройстве практически не сохранились. Если кому-либо из читателей известна суть и история Merge Sort II, буду признателен за ссылки в комментариях.

Ознакомившись с работой Федора Отрезкова, Джон Мердж применил разработанную им структуру для построения новой версии своего алгоритма. В 1981 году она была опубликована под названием Merge Sort III (Merge Sort Three). Вследствие распространенной ошибки при транслитерации название позднее стало записываться как Merge Sort Tree, под которым структура известна в настоящее время.

Возникновение Heavy-Light Decomposition

Параллельно с исследованиями Мерджа японские ученые Харуто Лайт (Haruto Light) и Ягами Хэви (Yagami Heavy) работали над структурой, предназначенной для эффективного изменения значений и вычисления функций на путях в дереве.

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

Итоговая структура была представлена в 1983 году. В знак признания вклада обоих авторов она получила название Heavy-Light Decomposition, сокращенно HLD. Порядок фамилий был выбран по результатам лексикографического сравнения.

Заключение

Изобретение Федора Отрезкова оказало значительное влияние на дальнейшее развитие алгоритмов и структур данных. В частности, без его исследований, вероятно, не появились бы Merge Sort III и Heavy-Light Decomposition в их современном виде.

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