Задачи RMQ и LCA

Задача и применение

RMQ (range minimum query) Выбор наименьшего элемента в отрезке индексов.

Дано: \(A = \{a_k \colon k < n \}\).

Операции:

• \(\rmq(i, j) = \min\{a_k \colon i \leqslant k \leqslant j\}\).

Задача и применение

LCA (less common ancestor) Выбор ближайшего общего предка.

Дано: дерево.

Операции:

• \(\lca(u, v) = w\) такое, что \(u \ll w\), \(v \ll w\) и для любого \(t \ll w\) следует, что либо \(u \not\ll t\), либо \(v \not\ll t\).

Задача и применение

</figcaption>

Задача и применение

Применение:

• суффиксное дерево;
• суффиксный массив;
• поиск по образцу;
• поисковые индексы;

RMQ -> LCA

Для элементов массива \(A\) определим

• ключ: \(k(a_k) = k\);
• приоритет: \(p(a_k) = a_k\);

Построим декартово дерево (\(O(n)\)):

• дерево поиска по ключам;
• куча по приоритету;

RMQ -> LCA

Offline LCA

Пусть все запросы известны заранее

Найдём все ответы за один проход по дереву (Tarjan).

1. Для каждой вершины выпишем все пары, с её участием.
2. Будем использовать post-order обход.
3. По мере обхода будем строить DDF.

Offline LCA

classDef zero  fill:tomato
classDef one   fill:darkorange
classDef two   fill:gold
classDef three fill:chartreuse

class A,B zero
class C,E,F one
class G,I two
class J three

</figcaption>

Offline LCA

При рассмотрении вершины \(x\) пройдёмся по всем парам с её участием.

Рассмотрим только те пары, где вторая вершина \(y\) уже просмотрена.

Решением этой пары будет корень дерева, содержащего \(y\).

Offline LCA

Online RMQ

Можно подсчитать результат для всех возможных запросов

Можно оставить только столбцы с номерами вида \(2^k\)

Online RMQ

\(\rmq(i, j)\)

• \(j - i = 2^k\) — результат уже есть в таблице
• выберем \(k = \max\{\ell \colon j - i > 2^\ell\}\), возьмём из таблицы \(\rmq(i, i + 2^k)\) и \(\rmq(j - 2^k, j)\). Выберем из них минимум.

±1 RMQ

±1 RMQ

Разобьём \(A\) на блоки \(B_\ell\) размера \(b\):

Логарифмическая таблица:

Запросы \(\rmq(i, j)\) делятся на 2 типа:

• \(i\) и \(j\) лежат в одном блоке;

• \(i\) и \(j\) лежат в разных блоках:

±1 RMQ

Сигнатура блока:

Построим таблицы для всех сигнатур: \(2^{b - 1} \times b \times b\)

±1 RMQ

±1 RMQ

Итого расход по памяти:

При \(b = \frac{\log n}{2}\):

LCA -> ±1 RMQ

</figcaption>

LCA -> ±1 RMQ

LCA -> ±1 RMQ

LCA -> ±1 RMQ

Рассмотрим последовательность глубин:

LCA -> ±1 RMQ

classDef zero  color:tomato
classDef one   color:steelblue
classDef two   color:blueviolet

class E zero
class C one
class A two

Рассмотрим последовательность глубин: