Решение RMQ с помощью разреженной таблицы

Материал из Викиконспекты
Перейти к: навигация, поиск

Разреженная таблица (англ. sparse table) позволяет решать задачу online static RMQ (получение минимума или максимума на отрезке, когда элементы массива не могут изменяться, а запросы поступают последовательно) за O(1) на запрос, с предподсчётом за O(N \log N) и использованием O(N \log N) памяти.


Задача:
Дан массив A[1 \ldots N] целых чисел. Поступают запросы вида (l, r), для каждого из которых требуется найти минимум среди элементов A[l], A[l + 1], \ldots, A[r].


Содержание

[править] Разреженная таблица

Разреженная таблица — двумерная структура данных ST[i][j], для которой выполнено следующее:

ST[i][j]=\min\left(A[i], A[i+1], \ldots, A[i+2^{j}-1]\right),\quad j \in [0 \ldots \log N].

Иначе говоря, в этой таблице хранятся минимумы на всех отрезках, длины которых равны степеням двойки. Объём памяти, занимаемый таблицей, равен O(N \log N), и заполненными являются только те элементы, для которых i+2^j \leqslant N.

Простой метод построения таблицы заключён в следующем реккурентном соотношении:

\displaystyle ST[i][j]= \begin{cases} \min\left(ST[i][j-1], ST[i+2^{j-1}][j-1]\right),&\text{если $j > 0$;}\\ A[i], &\text{если $j = 0$;} \end{cases}

[править] Идемпотентность

Такая простота достигается за счет идемпотентности операции минимум: \min(a, a)=a. Это один из ключевых моментов этого метода, так как она позволяет нам корректно считать минимум в области пересечения отрезков.


Пусть \circ — произвольная бинарная операция, которая удовлетворяет свойствам:

  • ассоциативности: a \circ (b \circ c) = (a \circ b) \circ c,
  • коммутативности: a \circ b = b \circ a,
  • идемпотентности: a \circ a = a.


Утверждение:
a_l \circ a_{l+1} \circ \ldots \circ a_r = (a_l \circ a_{l+1} \circ \ldots \circ a_k) \circ (a_{r - k} \circ a_{r - k + 1} \circ \ldots \circ a_r), где l \leqslant k \leqslant  r.
\triangleright
Отрезок (a_{r-k}, a_k) содержится в обоих операндах правой части. Значит, каждый элемент из него входит два раза. По коммутативности мы можем располагать элементы в любом порядке, по ассоциативности мы можем выполнять операции в произвольном порядке, поэтому повторяющие в правой части элементы мы можем расположить рядом друг с другом и затем по идемпотентности один из них убрать. Переставляя оставшиеся элементы в правой затем легко получаем выражение в левой части.
\triangleleft


[править] Применение к задаче RMQ

Предпосчитаем для длины отрезка l величину \lfloor \log_2l \rfloor. Для этого введем функцию fl (от floor, т.к. логарифм округляется вниз):
int fl(int len):
    if len = 1
        return 0
    else
        return fl(\lfloor \cfrac{len}{2}\rfloor) + 1

Вычисление fl[l] происходит за O(\log (l)). А так как длина может принимать N различных значений, то суммарное время предпосчета составляет O(N\log N).

Пусть теперь дан запрос (l, r). Заметим, что \min(A[l], A[l+1], \ldots, A[r]) = \min\left(ST[l][j], ST[r-2^j+1][j]\right), где j = \max \{k \mid 2^k \leqslant r - l + 1\}, то есть логарифм длины запрашиваемого отрезка, округленный вниз. Но эту величину мы уже предпосчитали, поэтому запрос выполняется за O (1).

Решение задачи RMQ на разреженной таблице

Из выше доказанной теоремы следует, что этот метод работает не только с операцией минимум, но и с любой идемпотентной, ассоциативной и коммутативной операцией. Таким образом мы получаем целый класс задач, решаемых разреженной таблицей.

[править] См. также

[править] Источники информации

  • Bender, M.A., Farach-Colton, M. et al.Lowest common ancestors in trees and directed acyclic graphs. — J. Algorithms 57(2) (2005) — с. 75–94.
Личные инструменты
Пространства имён
Варианты
Действия
Навигация
Инструменты