Решение RMQ с помощью разреженной таблицы — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Идемпотентность)
(Идемпотентность)
Строка 29: Строка 29:
 
$a_l \circ a_{l+1} \circ \dots \circ a_r = (a_l \circ a_{l+1} \circ \dots \circ a_k) \circ (a_{r - k} \circ a_{r - k + 1} \circ \dots \circ a_r)$, где $l \leqslant k \leqslant  r$.
 
$a_l \circ a_{l+1} \circ \dots \circ a_r = (a_l \circ a_{l+1} \circ \dots \circ a_k) \circ (a_{r - k} \circ a_{r - k + 1} \circ \dots \circ a_r)$, где $l \leqslant k \leqslant  r$.
 
|proof=
 
|proof=
Покажем, что $a \circ b \circ c \circ d = (a \circ b \circ c) \circ (b \circ c \circ d)$. Действительно, $a \circ b \circ c \circ b \circ c \circ d = a \circ b \circ b \circ c \circ c \circ d = a \circ b \circ c \circ d $. Будем применять это к выражению в правой части равенства до тех пор, пока не получим выражение в левой части. Поле каждого шага количество одинаковых элементов сократится на два. А так как их конечное четное число, то и количество шагов будет конечным.
+
Покажем, что $a \circ b \circ c \circ d = (a \circ b \circ c) \circ (b \circ c \circ d)$. Действительно, $a \circ b \circ c \circ b \circ c \circ d = a \circ b \circ b \circ c \circ c \circ d = a \circ b \circ c \circ d $. Будем применять это к выражению в правой части равенства до тех пор, пока не получим выражение в левой части. Поле каждого шага количество одинаковых элементов сократится на два. А так как их конечное четное (по $2k - r$ в каждой скобке) число, то и количество шагов будет конечным.
 
}}
 
}}
 
Таким образом мы получаем целый класс задач, которые могут решаться разреженной таблицей.
 
Таким образом мы получаем целый класс задач, которые могут решаться разреженной таблицей.

Версия 01:40, 16 апреля 2012

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

Постановка задачи RMQ

Дан массив [math]A[1..N][/math] действительных чисел. Поступают запросы вида [math](l, r)[/math]: найти минимум в подмассиве [math]A[l], A[l + 1], \dots, A[r] [/math].

Разреженная таблица

Разреженная таблица — двумерная структура данных [math]ST[i, j][/math], для которой выполнено следующее: [math]ST[i][j]=\min\left(A[i], A[i+1], ..., A[i+2^{j}-1]\right),\quad j \in [0 .. \log N][/math]. Иначе говоря, в этой таблице хранятся минимумы на всех отрезках, длины которых равны степеням двойки. Объём, занимаемый таблицей, равен [math]O(N \log N)[/math], и заполненными являются только те элементы, для которых [math]i+2^j \le N [/math].

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

[math] ST[i][j] = \left\{ \begin{array}{rcl} \min\left(ST[i][j-1], ST[i+2^{j-1}][j-1]\right), j \gt 0 \\ A[i], j = 0 \\ \end{array} \right. [/math] .

Идемпотентность

Такая простота достигается за счет идемпотентности операции минимум: [math]\min(a, a)=a[/math]. Это один из ключевых моментов этого метода, так как она позволяет нам корректно считать минимум в области пересечения отрезков. <wikitex> Пусть $\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 \dots \circ a_r = (a_l \circ a_{l+1} \circ \dots \circ a_k) \circ (a_{r - k} \circ a_{r - k + 1} \circ \dots \circ a_r)$, где $l \leqslant k \leqslant r$.
[math]\triangleright[/math]
Покажем, что $a \circ b \circ c \circ d = (a \circ b \circ c) \circ (b \circ c \circ d)$. Действительно, $a \circ b \circ c \circ b \circ c \circ d = a \circ b \circ b \circ c \circ c \circ d = a \circ b \circ c \circ d $. Будем применять это к выражению в правой части равенства до тех пор, пока не получим выражение в левой части. Поле каждого шага количество одинаковых элементов сократится на два. А так как их конечное четное (по $2k - r$ в каждой скобке) число, то и количество шагов будет конечным.
[math]\triangleleft[/math]

Таким образом мы получаем целый класс задач, которые могут решаться разреженной таблицей. </wikitex>

Применение к задаче RMQ

Решение задачи RMQ на разреженной таблице
Дан запрос [math](l, r)[/math]. По нему найдем [math]k = \max \{j| 2^j \le r - l + 1\}[/math], т.е. логарифм длины запрашиваемого отрезка. Заметим, что [math]k[/math] зависит лишь от длины отрезка. Предпосчитать эту величину за [math]O(N\log N)[/math] можно введением функции [math]fl[l] = k[/math], для которой верно [math]fl[1] = 0, fl[x] = fl[\lfloor \frac{x}{2}\rfloor] + 1[/math]. Далее заметим, что [math]\min(A[l], A[l+1], ..., A[r]) = \min\left(ST[l][k], ST[r-2^k+1][j]\right)[/math]. Таким образом мы можем находить [math]k[/math] за [math]O(1)[/math].

См. также

Источники

  • Bender, M.A., Farach-Colton, M. et al.Lowest common ancestors in trees and directed acyclic graphs. — J. Algorithms 57(2) (2005) — с. 75–94.