Постановка задачи
Здесь будут изучены два малосвязанных, на первый взгляд, вопроса: задача о минимуме на отрезке (range minimum query, RMQ) и задача о наименьшем общем предке (least common ancestor, LCA). Хотя их формулировки кажутся совершенно непохожими друг на друга, эти задачи тесно связаны.
Начнем с задачи RMQ. Пусть зафиксирована последовательность из n вещественных чисел A = (a1, …, an). Требуется реализовать структуру данных, которая по заданной паре (i, j) будет находить индекс k на отрезке [i, j], отвечающее которому значение ak минимально. Конечно, такой индекс можно найти, перебрав все возможные значения (количество которых j − i + 1). Такой алгоритм будем называть прямым вычислением. Сложность ответа на запрос при таком подходе оценивается как O(n). Оказывается, существуют намного более эффективные решения, к изучению которых мы и переходим.
Динамическая задача RMQ, деревья отрезков
Помимо запросов на поиск минимума на отрезке можно также разрешить операцию Change(i, x), которая изменяет i-й элемент последовательности A, присваивая ему значение x. Когда имеют в виду возможность менять A, говорят о динамической задаче.
Один из стандартных способов получить решение — это использовать специальную структуру данных, называемую деревом отрезков. Это дерево является бинарным и строится для массива длины n следующим образом. Каждая вершина дерева v задает некоторый непрерывный отрезок массива, обозначаемый ∆(v). Корню отвечает отрезок [1, n], покрывающий весь массив. Рассмотрим теперь произвольную вершину v, и пусть ∆(v) = [l, r]. Если l = r, то v является листом. В противном случае v имеет двух сыновей x и y, причем
Таким образом, листья дерева непосредственно соответствуют элементам массива, а вершины, находящиеся на более высоких уровнях, задают отрезки большей длины. При переходе от вершины к детям текущий отрезок разбивается на две равные (или почти равные) части. Очевидно, что высота построенного дерева составляет O(log n).
Отрезки массива, отвечающие вершинам дерева, будем называть каноническими. Оказывается, справедливо следующее утверждение.
Лемма 7.2.1. Любой отрезок ∆ может быть представлен в виде дизъюнктного объединения непересекающихся канонических отрезков ∆1, …, ∆k, где k = O(log n).
Доказательство. Утверждение о том, что любой отрезок можно разбить на канонические, само по себе тривиально: достаточно взять разбиение на одноэлементные множества. Интерес представляет возможность разбить на небольшое количество канонических отрезков.
Для доказательства опишем рекурсивную процедуру Decompose, которая строит искомое разбиение заданного отрезка ∆. Помимо самого отрезка, на вход ей будем также передавать вершину v, для которой будет выполнено условие ∆ ⊆ ∆(v). Итак, полная сигнатура процедуры имеет вид Decompose(∆, v).
Изначально v представляет собой корень дерева. Decompose поступает следующим образом. Если ∆ = ∅, то искомое разбиение пусто. Если ∆ = ∆(v), то разбиение состоит из одного отрезка. Иначе ясно, что v не может быть листом. Пусть, как и ранее, x и y обозначают левого и правого (соответственно) сыновей вершины v. Для построения разложения ∆ рассмотрим отрезки ∆x := ∆ ∩ ∆(x) и ∆y := ∆ ∩ ∆(y). Они вложены в ∆(x) и ∆(y), поэтому для построения их разложений произведем рекурсивные вызовы Decompose(∆x, x) и Decompose(∆y , y) и объединим их результаты.
Корректность процедуры очевидна. Оценим теперь количество слагаемых в разложении. Очевидно, количество таковых не превосходит общего числа вызовов процедуры Decompose, которые нам придется произвести. Докажем, что их количество составляет O(log n).
Сначала предположим, что произведен вызов простой процедуры Decompose(∆, v), т. е. у отрезков ∆ и ∆(v) общий левый или правый конец. Тогда несложно видеть, что при разложении ∆ мы произведем O(log n) рекурсивных вызовов. (Каждый раз, когда процесс вычисления разветвляется «налево» и «направо», либо «правый» вызов получает для разложения пустой отрезок, либо «левый» — канонический отрезок.) Аналогичное наблюдение справедливо для случая, когда правые концы отрезков ∆ и v совпадают.
Рассмотрим теперь общий случай. Назовем вершину v существенной, если для нее был произведен вызов процедуры Decompose, причем он потребовал использования рекурсии (и тем самым свелся к вызову для левого сына x и правого сына y). Если процедура Decompose была вызвана для несущественной вершины v, то ее родитель (если v не корень) уже должен быть существенным. Таким образом, достаточно доказать, что в дереве O(log n) существенных вершин.
Рассмотрим корень дерева. Если он несущественный, то доказательство завершено. Будем спускаться вниз от корня, до тех пора пока у текущей вершины есть ровно один существенный сын.
Мы можем остановиться по двум причинам. Во-первых, пусть у последней вершины v нет существенных сыновей. Тогда все существенные вершины дерева образуют путь от корня до v, и, очевидно, он имеет длину O(log n).
Иначе у вершины v оба сына x и y существенные. Пусть ∆ обозначает отрезок, который подлежал разложению при входе в v. Как и ранее, пусть ∆x := ∆ ∩ ∆(x) и ∆y := ∆ ∩ ∆(y). Тогда, поскольку x и y существенны, ∆ ∩ ∆x ≠∅ и ∆ ∩ ∆y ≠ ∅. Таким образом, если обозначить ∆(v)=[lv, rv], ∆(x)=[lx, rx], ∆(y) = [ly, ry] и ∆ = [l, r], то окажется справедливым условие
Таким образом, осталось выполнить два простых вызова процедур: Decompose(∆x,x) и Decompose(∆y,y). Как уже было показано, оба они посетят логарифмическое число вершин.
Описанный метод построения разложения вполне алгоритмичен и, будучи реализованным, требует O(log n) времени. Теперь осталось сделать совсем немногое, чтобы получить решение задачи RMQ. Свяжем с каждой вершиной v число m(v), равное минимуму среди значений массива A по каноническому отрезку ∆(v).
Если массив A нам задан изначально, то построить числа m можно снизу вверх, произведя обход дерева отрезков. Для листа v справедливо соотношение
Для внутренней вершины v имеем
Если содержимое ячейки ai изменяется, то потребуется обновить числа m. Для этого спустимся от корня по пути v1, …, vk , перечислив все отрезки, накрывающие точку i. Применим к этим вершинам соотношения выше, восстановив корректные значения m. Данная операция потребует времени O(log n).
Отметим, что для представления дерева в памяти не нужно хранить указатели на левого, правого сына или родителя. Вместо этого можно воспользоваться представлением бинарных деревьев в виде массива. При этом, конечно, нужно позаботиться о том, чтобы дерево отрезков было почти полным. Мы оставляем подробности читателю в качестве упражнения.
Кроме того, рассмотренная конструкция является совершенно общей и может быть применена не только для поиска минимума. Несложно видеть, что данный метод без изменения переносится на случай произвольной ассоциативной бинарной операции. Например, с помощью дерева отрезков можно решать задачу RSQ (range sum query), в которой вместо минимума берется сумма элементов.
Упражнение. Реализуйте алгоритмы задач RMQ и RSQ, представив дерево отрезков в виде массива.
Список литературы
- Бабенко М. А., Левин М. В. Введение в теорию алгоритмов и структур данных. Электронное издание М.: МЦНМО, 2016. с. 115–118. Книга доступна в нашей группе по ссылке.