Дерево отрезков является одной из наиболее значимых структур данных в современном олимпиадном программировании. Сегодня оно широко применяется для эффективного выполнения запросов на подотрезках массива, однако история его возникновения и дальнейшего влияния на алгоритмическую науку известна далеко не всем.
Изобретение дерева отрезков
История дерева отрезков берет начало в 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 в их современном виде.
Если вам известны другие интересные истории, связанные с изобретением алгоритмов и структур данных, буду рад увидеть их в комментариях.
Занимательно!
Спасибо за статью, было очень интересно, приятно знать что остались люди которые знают про Merge Sort II. Очень интересно было бы узнать у такого образованного человека про историю XOR III, Segment II и Sparse Chair
Добрый день! Спасибо за столь увлекательный рассказ из истории информатики. Буду рад увидеть следующие части! Насчёт Merge Sort II: недавно увидел на YouTube видеорасследование, посвещённое поиску следов этого алгоритма. Может, оно натолкнёт вас на нужную тропу: https://youtu.be/dQw4w9WgXcQ
Извините, но вы забыли упомянуть о работах Корнева. Я уверен, что Фёдор изучил его труды и попробовал на практике перед тем, как строить своё дерево. После окончания Второй мировой войны перед европейской наукой стояло множество сложных задач: восстановление городов, развитие промышленности и, что особенно важно, обработка массивов длины $$$n$$$.
В 1947 году молодой математик из Праги Радик Корнев получил в распоряжение длинную таблицу с показателями производства кирпича. Руководство требовало регулярно вычислять сумму значений на произвольных отрезках таблицы, однако полный перебор занимал слишком много времени, а использование сумм Джорджо Префикса не позволяло удобно учитывать еженедельные изменения плана.
Первые попытки Корнева были весьма прямолинейны. Он делил таблицу на два блока, затем на три, затем на все числа от $$$1$$$ до $$$n$$$. В ходе экспериментов учёный заметил: если размер блока сделать примерно равным $$$\sqrt{n}$$$, то количество блоков также окажется порядка $$$\sqrt{n}$$$. Это обстоятельство настолько поразило математика, что он несколько дней не выходил из кабинета, проверяя, не является ли оно ошибкой округления.
Открытие метода
В 1949 году Корнев представил метод «разложения таблиц Корнева». Идея была проста:
Таким образом, запрос на отрезке стал работать не за $$$O(n)$$$, а за примерно $$$O(\sqrt{n})$$$. По современным меркам это было не слишком быстро, однако в те годы большинство запросов всё ещё выполнялось методом «посмотреть на все элементы и немного подумать».
Метод получил название Декомпозиция Корнева в честь Корнева. Позднее англоязычные авторы ошибочно решили, что фамилия автора относится к квадратному корню, и стали называть структуру sqrt decomposition. Историческая справедливость до сих пор не восстановлена.