Алгоритм Фараха-Колтона и Бендера
Задача RMQ (Range Minimum Query) состоит в том, что на вход дан массив длины $n$ и $q$ запросов (отрезков этого массива), и необходимо для каждого запроса найти минимум на соответствующем отрезке массива. Есть много подходов к решению этой задачи. Есть тупое решение, которое работает за $O(n \cdot q)$, есть решение деревом отрезков, работающее за $O(n + q \log n)$, есть решение при помощи разреженных таблиц, работающее за $O(n \log n + q)$, и так далее. В этой статье мы рассмотрим подход, который нужен для этой конкретной задачи (дерево отрезков, к примеру, применимо для практически любых операций) и при этом работает за линейное время, а также альтернативный подход, который одновременно легче в реализации и быстрее на практике.
Стоит обратить внимание на то, что данная задача может ставиться в двух формулировках: offline и online. Offline означает, что все запросы даны заранее, и можно находить на них ответы в произвольном порядке. Однако в online версии задачи следующий запрос дается только после ответа на предыдущий. Мы рассмотрим обе версии задачи.
Кроме того, эту задачу можно делить на static и dynamic версии. В static версии массив фиксирован, а в dynamic версии могут приходить запросы изменения массива. Мы будем рассматривать именно static версию задачи.
RMQ offline. Вариация алгоритма Тарьяна за $O(\alpha(n))$ на запрос.
Ознакомиться с алгоритмом можно в соответствующей статье.
С первого взгляда это может показаться не очень ясным, но данный алгоритм имеет очень интересную связь с оригинальным алгоритмом Тарьяна для поиска LCA в дереве. Более глубокая связь между этими двумя алгоритмами станет понятна, когда мы разберем алгоритм Фараха-Колтона и Бендера (ФКБ), а пока можете воспринимать данный алгоритм как самостоятельный.
RMQ online. Улучшаем разреженные таблицы.
Разреженные таблицы хорошо подходят для решения задачи RMQ, потому что отвечают на запрос за константное время. Однако проблема в том, что на их построение уходит $O(n \log n)$ времени и памяти. В дальнейшем мы будем пытаться бороться с этим.
Давайте применим идею, схожую с идеей корневой декомпозиции. Разобьем массив на блоки. Однако длина блока будет не $\sqrt{n}$, а порядка $\log n$. Тогда количество блоков будет равно $\frac{n}{\log n}$. Давайте на каждом блоке за линейное время найдем минимум и на получившемся сжатом массиве построим разреженную таблицу. Ее построение займет $O\left(\frac{n}{\log n} \log \left( \frac{n}{\log n} \right)\right) = O\left( \frac{n}{\log n} \log n \right) = O(n)$ времени. Теперь мы умеем отвечать на запросы поиска минимума в том случае, если концы отрезка совпадают с концами блоков. Но что делать, если это не так?
Так же, как и в случае корневой декомпозиции, можно заметить, что любой отрезок запроса разбивается на несколько целых блоков, а также по краям слева и справа будут нецелые блоки. Для целых блоков мы можем найти минимум, используя нашу разреженную таблицу, остается найти минимум на маленьких кусочках слева и справа. Можно просто пройтись по ним и насчитать минимум. Так как длина блока — $O(\log n)$, то асимптотика ответа на запрос будет $O(\log n)$, но можно сделать и лучше.
Давайте заметим, что нам надо уметь искать минимумы на префиксах и суффиксах блоков. Все эти значения можно предпосчитать заранее за $O(n)$ (для каждого элемента массива сохранить минимум до конца и до начала его блока), тогда на запросы мы будем отвечать за $O(1)$, ведь минимум на отрезке — это минимум из трех величин: минимум на суффиксе левого неполного блока, минимум в разреженной таблице по целым блокам и минимум на префиксе правого неполного блока.
Упражнение: Почему же на этом статья не заканчивается, а только начинается? Стоит задуматься над этим вопросом, чтобы проверить свое понимание происходящего.
На самом деле, к сожалению, этого не достаточно. И проблема находится там, где ее не ждали: в маленьких отрезках. Действительно, если длина отрезка запроса не меньше логарифма, то он обязательно состоит из нескольких (возможно, нуля) целых блоков, одного префикса и одного суффикса. Но для маленьких отрезочков это может быть неверно в том случае, если отрезок целиком лежит внутри блока. Тогда он не разбивается на префикс и суффикс, да и внутренних целых блоков у него тоже нет.
Стоит помнить о том, что все последующие манипуляции, которые мы будем производить, нужны именно для того, чтобы побороть маленькие отрезки. Уже сейчас мы можем просто пройтись по этим отрезкам за линию и найти минимум, тогда для больших отрезков мы будем отвечать на запрос за $O(1)$, а для маленьких за $O(\log n)$, потому что их длина не больше логарифма.
Можно пойти с другой стороны и заметить, что маленьких отрезков не больше $n \log n$ штук (для каждой левой границы существует $\le \log n$ маленьких отрезков), поэтому для них всех можно предпосчитать ответы заранее за $O(n \log n)$ и отвечать на запросы за $O(1)$, однако мы опять упираемся в проблему: либо в построении вылезает логарифм, либо при ответе на запрос. Мы же хотим избавиться от логарифмов полностью.
RMQ$\pm 1$ online. Маленьких отрезков становится мало.
Давайте для начала решим упрощенную версию задачи RMQ, после чего сведем общий случай к простому.
Простая версия (RMQ$\pm 1$) отличается от обычной задачи RMQ тем, что в данном нам массиве соседние элементы обязательно отличаются друг от друга на $\pm 1$. Как же это нам поможет искать минимум на маленьких подотрезках?
Давайте заметим, что позиция минимума на отрезке определяется только разностями соседних элементов и не зависит от самих значений этих элементов. К примеру, можно считать, что первый элемент отрезка равен нулю (как будто мы вычли из всех элементов на отрезке первый), и в таком массиве минимум будет стоять на той же самой позиции, что и в изначальном. Поменяется лишь его значение. Но если мы найдем позицию минимума, найти его значение не составит труда: нужно лишь обратиться к соответствующему индексу изначального массива.
Теперь заметим, что если мы превратим все блоки в последовательности разностей соседних элементов, то эти последовательности будут состоять из чисел $1$ и $-1$, тогда если длина блока равна $k$, то существует всего $2^{k - 1}$ различных последовательностей разностей соседних элементов. После чего мы можем заранее предпосчитать для каждой такой последовательности минимум на каждом подотрезке. На это уйдет $O(2^{k - 1} \cdot k^2)$ времени. И затем просто для каждого блока в массиве определить, к какому типу он относится, и пользоваться предпосчитанными значениями позиций минимумов для всех маленьких подотрезков для ответа на запросы в будущем.
Остается лишь выбрать число $k$ так, чтобы $2^{k - 1} \cdot k^2$ было не больше $n$, и при этом разреженная таблица на блоках длины $k$ строилась все еще за $O(n)$. Давайте возьмем $k = \frac{\log n}{2}$. В таком случае
$$2^{k - 1} \cdot k^2 \le 2^k \cdot k^2 = 2^{\frac{\log n}{2}} \cdot \log^2 n = n^{\frac{1}{2}} \cdot \log^2 n = \sqrt{n} \log^2 n$$
Это, безусловно, асимптотически меньше, чем $n$.
С точки зрения реализации можно представлять любой блок длины $k - 1$ из $\pm 1$ как битовую маску длины $k - 1$ ($+1$ — единичный бит, $-1$ — нулевой бит), тогда после начального предпосчета можно будет для подотрезков изначального массива находить такую же маску и легко определять, к какому типу относится текущий блок. Предпосчет же будет просто храниться в трехмерном массиве размера $2^{k - 1} \times k \times k$. Кроме того, нам больше не надо хранить отдельно минимумы на префиксах и суффиксах блоков, потому что теперь у нас есть минимумы на вообще всех подотрезках внутри блоков. Также можно в предпосчете хранить все таки не позицию, а значение минимума на соответствующем подотрезке при условии, что первый элемент равен нулю, если вам нужно только значение минимума, а не его позицию. Тогда при ответе на запрос надо будет просто прибавить к ответу элемент на левой границе отрезка.
Реализация доступна по ссылке.
Наиболее эффективная реализация доступна по ссылке.
Сведение LCA к RMQ$\pm 1$.
RMQ$\pm 1$ — весьма специфичная задача, однако, вероятно, вы уже с ней встречались. Один из алгоритмов поиска LCA в дереве сводит LCA к RMQ при помощи выписывания эйлерова обхода дерева. После этого обычно используется разреженная таблица для поиска минимума на отрезке. Однако можно заметить, что в эйлеровом обходе соседние вершины соединены ребром, поэтому разность их глубин в точности равна $\pm 1$, так что на самом деле LCA сводится к задаче RMQ$\pm 1$, поэтому мы научились решать задачу LCA online за $O(n + q)$.
Реализация доступна по ссылке.
Сведение RMQ к LCA.
А теперь наступает неожиданный поворот. Мы сведем общий случай задачи RMQ к задаче LCA. А задачу LCA мы уже умеем сводить к задаче RMQ$\pm 1$, которую мы умеем решать за $O(n + q)$. То есть такой странной последовательностью сведений мы научимся решать общий случай задачи RMQ за $O(n + q)$.
Само сведение тоже может показаться весьма странным и удивительным. Пускай у нас есть массив $A$. Давайте построим декартово дерево, в котором ключами будут числа от $0$ до $n - 1$, а приоритетами будут элементы массива $A$ (в корне находится минимальный элемент). То есть построим декартово дерево на парах $(i, A_i)$. В общем случае построить декартово дерево за $O(n)$ невозможно, потому что это бы решало задачу сортировки массива за $O(n)$, но в нашем случае ключи — это числа от $0$ до $n - 1$, так что они уже отсортированы. В случае отсортированных ключей декартово дерево можно без труда построить за $O(n)$. Алгоритм мы обсудим позже.
Теперь остается только заметить, что минимум на отрезке от $l$ до $r$ как раз таки соответствует LCA вершин с ключами $l$ и $r$ в нашем декартовом дереве. Действительно, LCA находится между левым и правым поддеревом по $x$ координате, значит, ключ LCA лежит между $l$ и $r$. С другой стороны, потенциал LCA является минимальным в его поддереве, а это поддерево содержит в себе весь подотрезок от $l$ до $r$, потому что оно содержит его границы. Так что это число лежит на нужном отрезке, а также является минимумом на нем. Что и требовалось доказать.
Осталось только научиться строить декартово дерево за $O(n)$ при условии, что ключи отсортированы. Давайте последовательно добавлять элементы в дерево по возрастанию ключей. Новый ключ будет обязательно самой правой вершиной дерева. Осталось только понять, куда его подвесить, и как перестроить дерево. Давайте посмотрим на предыдущую вершину, которую мы добавили. Если потенциал новой вершины меньше или равен, чем потенциал предыдущей, то ее нужно просто подвесить к предыдущей вершине справа (так как у нее точно нет еще правого сына). Если же потенциал новой вершины меньше потенциала предыдущей вершины, нужно идти от нее наверх в сторону корня, пока мы не встретим первую вершину, у которой потенциал будет уже больше или равен потенциала новой вершины. Пускай мы добавляем в дерево вершину $v$, у вершины $u$ потенциал меньше, чем у $v$, а у отца $p$ вершины $u$ потенциал уже не меньше потенциала $v$. Тогда теперь правым сыном вершины $p$ будет являться вершина $v$, а вершину $u$ надо подвесить левым сыном вершины $v$, то есть вершина $v$ влезла внутрь ребра $p \to u$. Если же такой вершины $p$ не существует, то есть у всех вершин потенциал меньше, чем у $v$, то $v$ просто станет новым корнем, а старый корень мы подвесим к ней как левого сына.
Весь этот процесс можно представлять как стек. Давайте хранить правую ветку декартова дерева в стеке. Этот стек очень похож на стек минимумов. Тогда когда пришла новая вершина, мы удаляем элементы из стека, пока их потенциалы меньше потенциала новой вершины, а потом добавляем новую вершину в стек, производя константное количество изменений в дереве. Так как каждая вершина добавится в стек (а значит, и удалится) ровно один раз, асимптотика алгоритма — $O(n)$.
Замечание: Теперь если вы вернетесь к решению, использующему вариацию алгоритма Тарьяна, вы сможете увидеть, что тот стек, который мы использовали, как раз таки и является стеком построения декартова дерева. Однако из-за устройства алгоритма Тарьяна, мы можем явно не строить никакого дерева и получить более простой алгоритм.
Реализация доступна по ссылке.
Наиболее эффективная реализация доступна по ссылке.
Упрощенная битовая вариация алгоритма ФКБ для практики
Мы добились теоретической линейности решения RMQ, однако, этот алгоритм весьма сложен в реализации из-за трех разных фаз, а также константа в асимптотике достаточно большая, так что данный алгоритм редко можно применить на практике. При решении оффлайн версии задачи стоит посмотреть в сторону вариации алгоритма Тарьяна. Чаще всего ее будет достаточно.
Однако если задачу все таки необходимо решать в онлайне, есть упрощенная версия алгоритма ФКБ без сведений к LCA и обратно к RMQ$\pm 1$. В остальном этот алгоритм похож на ФКБ. Мы все так же будем делить массив на блоки и строить разреженную таблицу на блоках. Остается научиться находить минимум на отрезках, лежащих внутри одного блока, альтернативным способом. Давайте добавим к нашему решению идею из offline решения. Пройдемся по массиву со стеком минимумов. Теперь нам остается решить две проблемы:
- Нужно сделать этот стек в некотором смысле персистентным, то есть чтобы мы могли обращаться к стеку минимумов на тот момент, когда мы находились в конкретном элементе.
- Нужно уметь за $O(1)$ находить ближайший справа элемент стека минимумов к левой границе отрезка запроса.
Но тут нам на помощь приходит тот факт, что нам надо искать минимумы только на отрезках длины $\le \frac{\log n}{2}$. Это число не больше $32$ при $n \le 2^{64} \sim 10^{19}$. Безусловно, в реальной задаче $n$ не может быть настолько большим. Тогда давайте хранить стек минимумов в весьма необычном формате. Давайте сохраним массив длины $32$, в котором для каждого из последних $32$ индексов массива будем хранить, лежит ли он в стеке минимумов или нет. Так как длина этого массива равна $32$, можно не хранить массив, а сохранить это просто как битовую маску в одном числе типа int. При переходе к следующей позиции нужно умножить эту маску на два, удалить те биты, которые пропали из стека минимумов, а также добавить новый элемент. Так что мы можем сохранить такой миниатюрный стек для каждой позиции массива, на это уйдет $O(n)$ времени и памяти.
Теперь нам остается решить вторую проблему. Как за $O(1)$ по такой битовой маске находить минимум на отрезке длины $\le 32$? Это можно сделать при помощи битовых операций. Если длина отрезка равна len, то применив к маске операцию побитового «и» с числом (1 << len) - 1, мы оставим только элементы стека минимумов, лежащие на отрезке запроса, после чего нужно найти самый первый из них. Это совпадает со старшим битом получившейся маски. Для нахождения старшего бита числа можно либо изначально предпосчитать динамику (насчитаем для всех чисел от $1$ до $2^{16}$ старшие биты, после чего число длины $32$ разбивается на два числа длины $16$), либо воспользоваться встроенной в C++ функцией __builtin_clz (Count Leading Zeros), которая возвращает за $O(1)$ (с достаточно быстрой константой) количество лидирующих нулей в числе. Тогда чтобы получить индекс старшего бита числа, нужно просто вычесть значение этой функции из числа $32$.
Асимптотика получившегося алгоритма — это вроде бы $O((n + q) \left \lceil \frac{\log n}{32} \right\rceil)$, но в действительности это $O(n + q)$, ведь при анализе времени работы алгоритмов мы всегда подразумеваем, что $n \le 2^w$, где $w$ — длина машинного слова ($32$ или $64$), потому что если это не так, то мы не сможем хранить индексы входного массива как числа. Но если $n \le 2^w$, то $\frac{\log n}{w} \le 1$, поэтому данный алгоритм работает за $O(n + q)$.
Замечание: Обратите внимание на то, что теперь длины блоков — $32$ вместо $\frac{\log n}{2}$, поэтому блоков стало меньше, и на построение разреженной таблицы уходит еще меньше времени. Кроме того, число $32$ является степенью двойки, поэтому деление на длину блока будет происходить быстрее.
Замечание:
Этот алгоритм можно оптимизировать по памяти. Нам необходимо хранить начальный массив длины $n$, массив миниатюрных стеков минимумов размера $n$, разреженную таблицу размера $\frac{n}{32} \log{\frac{n}{32}}$, а также обычный стек минимумов в процессе построения миниатюрных стеков. Изначальный массив и массив миниатюрных стеков нам необходимы, а вот от лишнего стека минимумов, использующегося в процессе построения, можно избавиться, ведь нам надо хранить лишь последние $32$ элемента. Это можно делать различными способами, но самый простой, пожалуй, — это заметить, что нам на самом деле достаточно лишь миниатюрного стека. Чтобы обратиться к вершине стека, нужно найти в маске самый младший бит. Это делается аналогично нахождению старшего бита при помощи функции __builtin_ctz (Count Trailing Zeros).
Реализация доступна по ссылке.
Наиболее эффективная реализация доступна по ссылке.
Этот алгоритм примерно в 2 раза быстрее алгоритма ФКБ, а также, что самое главное, использует как минимум в $5$ раз меньше памяти (есть реализации алгоритма ФКБ, которые работают не сильно медленнее приведенного алгоритма и тратят не сильно больше памяти, однако их реализации еще сложнее, чем оригинальный ФКБ).
Однако эффективная реализация дерева отрезков снизу (Смотрите здесь) хоть и использует $O(\log n)$ времени на запрос, но на практике работает за такое же время (на удивление даже если менять ограничения, разность во времени работы получается крайне маленькой), а также тратит немного меньше памяти (примерно на четверть). Кроме того, его еще легче реализовать, а также оно может работать не только со static версией задачи, но и с динамической (к примеру, можно делать присвоение в точке).
Эффективная реализация дерева отрезков снизу доступна по ссылке.