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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Идемпотентность)
м (Правка орфографии)
(не показано 15 промежуточных версий 6 участников)
Строка 1: Строка 1:
'''Разреженная таблица''' (англ. ''sparse table'') позволяет решать задачу online static RMQ за <tex>O(1)</tex> на запрос, с предподсчётом за <tex>O(N \log N)</tex> и использованием <tex>O(N \log N)</tex> памяти.
+
'''Разреженная таблица''' (англ. ''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>.
+
{{Задача
 +
|definition = Дан массив <tex>A[1 \ldots N]</tex> целых чисел. Поступают запросы вида <tex>(l, r)</tex>, для каждого из которых требуется найти минимум среди элементов <tex>A[l], A[l + 1], \ldots, A[r] </tex>.
 +
}}
  
 
== Разреженная таблица ==
 
== Разреженная таблица ==
Разреженная таблица — двумерная структура данных <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]</tex>, для которой выполнено следующее:  
 +
 
 +
<tex>ST[i][j]=\min\left(A[i], A[i+1], \ldots, A[i+2^{j}-1]\right),\quad j \in [0 \ldots \log N]</tex>.  
 +
 
 +
Иначе говоря, в этой таблице хранятся минимумы на всех отрезках, длины которых равны степеням двойки. Объём памяти, занимаемый таблицей, равен <tex>O(N \log N)</tex>, и заполненными являются только те элементы, для которых <tex>i+2^j \leqslant N </tex>.
  
Простой метод построения таблицы заключён в следующем реккурентном соотношении:  
+
Простой метод построения таблицы заключён в следующем рекуррентном соотношении:
 +
$$
 +
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}
 +
$$
  
<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 \circ c) = (a \circ b) \circ c $,
* коммутативности: $a \circ b = b \circ a$;
+
* коммутативности: $a \circ b = b \circ a$,
 
* идемпотентности: $a \circ a = a $.
 
* идемпотентности: $a \circ a = a $.
  
Строка 27: Строка 32:
 
{{Утверждение
 
{{Утверждение
 
|statement=
 
|statement=
$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; \frac{l}{2} \leqslant k$.
+
$a_l \circ a_{l+1} \circ \ldots \circ a_r = (a_l \circ a_{l+1} \circ \ldots \circ a_{l + k}) \circ (a_{r - k} \circ a_{r - k + 1} \circ \ldots \circ a_r)$, где $\frac{r - l}{2} \leqslant k \leqslant  r - l$.
 
|proof=
 
|proof=
Отрезок $(a_{r-k}, a_k)$ содержится в обои операндах правой части. Значит, каждый элемент из него входит два раза. По коммутативности мы можем расположить повторяющиеся элементы друг с другом. По ассоциотивности мы можем расставлять скобки как угодно, в том числе, обособляя эти самые повторы. А за счет идемпотентности мы от них избавляемся. В итоге, получаем выражение в левой части равенства.
+
Отрезок $(a_{r-k}, a_{l + k})$ содержится в обоих операндах правой части. Значит, каждый элемент из него входит два раза. По коммутативности мы можем располагать элементы в любом порядке, по ассоциативности мы можем выполнять операции в произвольном порядке, поэтому повторяющие в правой части элементы мы можем расположить рядом друг с другом и затем по идемпотентности один из них убрать. Переставляя оставшиеся элементы в правой затем легко получаем выражение в левой части.
 
}}
 
}}
</wikitex>
 
  
 
== Применение к задаче RMQ ==
 
== Применение к задаче RMQ ==
 +
 +
<div> Предпосчитаем для длины отрезка <tex>l</tex> величину <tex>\lfloor \log_2l \rfloor</tex>. Для этого введем функцию <tex>fl</tex> (от ''floor'', т.к. логарифм округляется вниз):
 +
 +
'''int''' '''fl'''('''int''' len):
 +
    '''if''' len <tex>=</tex> 1
 +
        '''return''' 0
 +
    '''else'''
 +
        '''return''' fl(<tex>\lfloor \cfrac{len}{2}\rfloor</tex>) + 1
 +
 +
Вычисление <tex>fl[l]</tex> происходит за <tex>O(\log (l))</tex>. А так как длина может принимать <tex>N</tex> различных значений, то суммарное время предпосчета составляет <tex>O(N\log N)</tex>.
 +
 +
Пусть теперь дан запрос <tex>(l, r)</tex>.  Заметим, что <tex>\min(A[l], A[l+1], \ldots, A[r]) = \min\left(ST[l][j], ST[r-2^j+1][j]\right)</tex>, где <tex>j = \max \{k \mid 2^k \leqslant r - l + 1\}</tex>, то есть логарифм длины запрашиваемого отрезка, округленный вниз. Но эту величину мы уже предпосчитали, поэтому запрос выполняется за <tex>O (1)</tex>.
 +
 
[[Файл: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>
  
Строка 47: Строка 60:
 
* [[Алгоритм Фарака-Колтона и Бендера | Алгоритм Фарака-Колтона и Бендера]]
 
* [[Алгоритм Фарака-Колтона и Бендера | Алгоритм Фарака-Колтона и Бендера]]
 
* [[Сведение задачи RMQ к задаче LCA | Сведение задачи RMQ к задаче LCA]]
 
* [[Сведение задачи RMQ к задаче LCA | Сведение задачи RMQ к задаче LCA]]
 +
* [[ Heavy-light декомпозиция |  Heavy-light декомпозиция]]
  
== Источники ==
+
== Источники информации==
 
* ''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.
 
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Задача о наименьшем общем предке]]
 
[[Категория: Задача о наименьшем общем предке]]

Версия 22:33, 5 сентября 2019

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


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


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

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

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

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

Простой метод построения таблицы заключён в следующем рекуррентном соотношении: $$ 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} $$

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

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

Пусть $\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_{l + k}) \circ (a_{r - k} \circ a_{r - k + 1} \circ \ldots \circ a_r)$, где $\frac{r - l}{2} \leqslant k \leqslant r - l$.
[math]\triangleright[/math]
Отрезок $(a_{r-k}, a_{l + k})$ содержится в обоих операндах правой части. Значит, каждый элемент из него входит два раза. По коммутативности мы можем располагать элементы в любом порядке, по ассоциативности мы можем выполнять операции в произвольном порядке, поэтому повторяющие в правой части элементы мы можем расположить рядом друг с другом и затем по идемпотентности один из них убрать. Переставляя оставшиеся элементы в правой затем легко получаем выражение в левой части.
[math]\triangleleft[/math]

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

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

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

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

Решение задачи 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.