Редактирование: Решение RMQ с помощью разреженной таблицы
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
− | '''Разреженная таблица''' (англ. ''sparse table'') позволяет решать задачу online static RMQ | + | '''Разреженная таблица''' (англ. ''sparse table'') позволяет решать задачу online static RMQ за <tex>O(1)</tex> на запрос, с предподсчётом за <tex>O(N \log N)</tex> и использованием <tex>O(N \log N)</tex> памяти. |
− | + | == Постановка задачи RMQ == | |
− | + | Дан массив <tex>A[1..N]</tex> действительных чисел. Поступают запросы вида <tex>(l, r)</tex>: найти минимум в подмассиве <tex>A[l], A[l + 1], \dots, A[r] </tex>. | |
− | |||
− | |||
== Разреженная таблица == | == Разреженная таблица == | ||
− | Разреженная таблица — двумерная структура данных <tex>ST[i | + | Разреженная таблица — двумерная структура данных <tex>ST[i, j]</tex>, для которой выполнено следующее: <tex>ST[i][j]=\min\left(A[i], A[i+1], ..., A[i+2^{j}-1]\right),\quad j \in [0 .. \log N]</tex>. Иначе говоря, в этой таблице хранятся минимумы на всех отрезках, длины которых равны степеням двойки. Объём, занимаемый таблицей, равен <tex>O(N \log N)</tex>, и заполненными являются только те элементы, для которых <tex>i+2^j \le N </tex>. |
− | |||
− | <tex>ST[i][j]=\min\left(A[i], A[i+1], | ||
− | |||
− | Иначе говоря, в этой таблице хранятся минимумы на всех отрезках, длины которых равны степеням двойки. Объём | ||
− | Простой метод построения таблицы заключён в следующем | + | Простой метод построения таблицы заключён в следующем реккурентном соотношении: |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | == Идемпотентность == | + | <tex> ST[i][j] = |
+ | \left\{ | ||
+ | \begin{array}{rcl} | ||
+ | \min\left(ST[i][j-1], ST[i+2^{j-1}][j-1]\right), j > 0 \\ | ||
+ | A[i], j = 0 \\ | ||
+ | \end{array} | ||
+ | \right. | ||
+ | </tex> . | ||
+ | === Идемпотентность === | ||
Такая простота достигается за счет идемпотентности операции минимум: <tex>\min(a, a)=a</tex>. Это один из ключевых моментов этого метода, так как она позволяет нам корректно считать минимум в области пересечения отрезков. | Такая простота достигается за счет идемпотентности операции минимум: <tex>\min(a, a)=a</tex>. Это один из ключевых моментов этого метода, так как она позволяет нам корректно считать минимум в области пересечения отрезков. | ||
− | + | <wikitex> | |
− | Пусть $\circ$ | + | Пусть $\circ$ - произвольная бинарная операция, которая удовлетворяет свойствам: |
− | * ассоциативности | + | * ассоциативности {{---}} $a \circ (b \circ c) = (a \circ b) \circ c $; |
− | * коммутативности | + | * коммутативности {{---}} $a \circ b = b \circ a$; |
− | * идемпотентности | + | * идемпотентности {{---}} $a \circ a = a $. |
{{Утверждение | {{Утверждение | ||
|statement= | |statement= | ||
− | $a_l \circ a_{l+1} \circ \ | + | $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 $. Будем применять это к выражению в правой части равенства до тех пор, пока не получим выражение в левой части. Поле каждого шага количество одинаковых элементов сократится на два. А так как их конечное четное число, то и количество шагов будет конечным. | |
}} | }} | ||
+ | Таким образом мы получаем целый класс задач, которые могут решаться разреженной таблицей. | ||
+ | </wikitex> | ||
== Применение к задаче RMQ == | == Применение к задаче RMQ == | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
[[Файл:SparseTableRMQ.png|right|Решение задачи RMQ на разреженной таблице]] | [[Файл:SparseTableRMQ.png|right|Решение задачи RMQ на разреженной таблице]] | ||
− | + | <div>Дан запрос <tex>(l, r)</tex>. По нему найдем <tex>k = \max \{j| 2^j \le r - l + 1\}</tex>, т.е. логарифм длины запрашиваемого отрезка. Заметим, что <tex>k</tex> зависит лишь от длины отрезка. Предпосчитать эту величину за <tex>O(N\log N)</tex> можно введением функции <tex>fl[l] = k</tex>, для которой верно <tex>fl[1] = 0, fl[x] = fl[\lfloor \frac{x}{2}\rfloor] + 1</tex>. | |
− | + | Далее заметим, что <tex>\min(A[l], A[l+1], ..., A[r]) = \min\left(ST[l][k], ST[r-2^k+1][j]\right)</tex>. Таким образом мы можем находить <tex>k</tex> за <tex>O(1)</tex>.</div> | |
<div style="clear:both"></div> | <div style="clear:both"></div> | ||
Строка 60: | Строка 44: | ||
* [[Алгоритм Фарака-Колтона и Бендера | Алгоритм Фарака-Колтона и Бендера]] | * [[Алгоритм Фарака-Колтона и Бендера | Алгоритм Фарака-Колтона и Бендера]] | ||
* [[Сведение задачи RMQ к задаче LCA | Сведение задачи RMQ к задаче LCA]] | * [[Сведение задачи RMQ к задаче LCA | Сведение задачи RMQ к задаче LCA]] | ||
− | |||
− | == Источники | + | == Источники == |
* ''Bender, M.A., Farach-Colton, M. et al.'' — '''Lowest common ancestors in trees and directed acyclic graphs'''. — J. Algorithms 57(2) (2005) — с. 75–94. | * ''Bender, M.A., Farach-Colton, M. et al.'' — '''Lowest common ancestors in trees and directed acyclic graphs'''. — J. Algorithms 57(2) (2005) — с. 75–94. | ||
+ | |||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Задача о наименьшем общем предке]] | [[Категория: Задача о наименьшем общем предке]] |