112
правок
Изменения
Новая страница: «'''2D Sparse Table''' - это структура данных, которая позволяет решать задачу online static RMQ. {{Задача |d...»
'''2D Sparse Table''' - это структура данных, которая позволяет решать задачу online static RMQ.
{{Задача
|definition = Дан двумерный массив <tex>A[1 \ldots N][1 \ldots M]</tex> целых чисел. Поступают запросы вида <tex>(x_1, y_1, x_2, y_2)</tex> такие, что <tex> x_1 <= x_2 </tex> и <tex> y_1 <= y_2 </tex> , для каждого из которых требуется найти минимум среди <tex>A[i][j], x_1 <= i <= x_2 </tex> и <tex> y_1 <= j <= y_2 </tex>.
}}
== Структура 2D Sparse Table ==
В целом структура 2D Sparse Table схожа со структурой обычной [[Решение_RMQ_с_помощью_разреженной_таблицы| разряженной таблице]]. Структура представляет собой четырехмерный массив <tex> ST[N][M][LOGN][LOGM], LOGN = \log(N), LOGM = \log(M) </tex>.
<tex>ST[i][j][k_1][k_2] = \min(A[i][j], A[i+1][j], \ldots, A[i+2^{k_1}-1][j] </tex>,
<tex>A[i][j + 1], A[i+1][j + 1], \ldots, A[i+2^{k_1}-1][j + 1], </tex>
<tex>\ldots \ldots\ldots\ldots\ldots</tex>,
<tex>A[i][j + 2^{k_2}-1], A[i+1][j + 2^{k_2}-1], \ldots, A[i+2^{k_1}-1][j + 2^{k_2}-1]),</tex> <tex> k_1 \in [0 \ldots \log N], k_2 \in [0 \ldots \log M] </tex>
То есть в ячейке структуры мы храним минимум для подматрицы, длины сторон которого являются некоторыми степенями двойки.
== Реализация 2D Sparse Table ==
'''Построение'''
Исходно полагаем, что все элементы структуры имеют значение <tex> inf </tex>.
Для начала необходимо присвоить элементам структуры, размеры которых <tex> 1 \times 1 </tex>, значения элементов исходной матрицы <tex> A </tex>.
'''for''' i : 1 to <tex> N </tex>
'''for''' j : 1 to <tex> M </tex>
<tex>ST[i][j][0][0] = A[i][j]</tex>
Далее мы считаем [[Решение_RMQ_с_помощью_разреженной_таблицы|1D Sparse Table]] для каждого столбца и строчки:
'''for''' lg : 1 to <tex> max(\log(N), \log(M)) </tex>
'''for''' i : 1 to <tex> N </tex>
'''for''' j : 1 to <tex> M </tex>
<tex>ST[i][j][lg][0] = min(ST[i][j][lg - 1][0], ST[i + 2^{lg}][j][lg - 1][0]);</tex>
<tex>ST[i][j][0][lg] = min(ST[i][j][0][lg - 1], ST[i][j+ 2^{lg}][0][lg - 1]);</tex>
Следующим шагом мы можем обновить значения для подматриц, так как для всех строк и столбцов ответы уже известны. Будем это делать по аналогичному алгоритму для 1D Sparse Table.
'''for''' <tex> k_1 </tex> : 1 to <tex> \log(N) </tex>
'''for''' <tex> k_2 </tex> : 1 to <tex> \log(M) </tex>
'''for''' i : 1 to <tex> N </tex>
'''for''' j : 1 to <tex> M </tex>
<tex>ST[i][j][k_1][k_2] = min(ST[i][j][k_1 - 1][k_2 - 1], ST[i + 2^{k_1}][j][k_1 - 1][k_2 - 1],</tex>
<tex>ST[i][j + 2^{k_2}][k_1 - 1][k_2 - 1], ST[i + 2^{k_1}][j + 2^{k_2}][k_1 - 1][k_2 - 1]) </tex>
Таким образом мы получили 2D Sparce Table за <tex>O(N * M * \log (N) * \log (M))</tex>
'''Ответы на запросы'''
Для ответа на запрос RMQ <tex> (l, r) </tex> в 1D Sparse Table использовалось пересечение отрезков <tex> [l, l + 2^{k}] </tex> и <tex> [r - 2^{k} + 1, r] </tex>, где <tex> k = \lfloor \log(SZ) \rfloor , SZ </tex> - размера массива для одномерной задачи.
Тут мы будем пользоваться аналогичным утверждением для матриц. Таким образов минимум на подматрице <tex>(x_1, y_1, x_2, y_2)</tex> будет высчитываться следующим образом:
<tex> k_1 = \lfloor \log(x_2 - x_1 + 1) \rfloor, k_2 = \lfloor \log(y_2 - y_1 + 1) \rfloor </tex>
<tex> ans = min(ST[x_1][y_1][k_1][k_2], ST[x_2 - 2^{k_1} + 1][y_1][k_1][k_2], </tex>
<tex> ST[x_1][y_2 - 2^{k_2} + 1][k_1][k_2], ST[x_2 - 2^{k_1} + 1][y_2 - 2^{k_2} + 1][k_1][k_2]) </tex>
Таким образом мы рассмотрим мы получаем ответ за <tex> O(1) </tex>, если предпосчитать логарифмы двоек, например так:
curLog = 0;
k = 1;
'''while ''' <tex> (k < max(N, M)) </tex>
lg[k] = curLog;
k = k * 2;
curLog = curLog + 1;
curLog = 0;
'''for''' k : 1 to <tex> max(N, M) </tex>
if (curLog != lg[k]) curLog = lg[k];
lg[k] = curLog;
----
При помощи 2D Sparse Table можно решать и некоторые другие задачи, например связанные с суммой на подматрице. ([[Решение_RMQ_с_помощью_разреженной_таблицы|Идемпотентность]])
== Источники информации==
[[Решение_RMQ_с_помощью_разреженной_таблицы| Идемпотентность]]
[[Категория: Алгоритмы и структуры данных]]
{{Задача
|definition = Дан двумерный массив <tex>A[1 \ldots N][1 \ldots M]</tex> целых чисел. Поступают запросы вида <tex>(x_1, y_1, x_2, y_2)</tex> такие, что <tex> x_1 <= x_2 </tex> и <tex> y_1 <= y_2 </tex> , для каждого из которых требуется найти минимум среди <tex>A[i][j], x_1 <= i <= x_2 </tex> и <tex> y_1 <= j <= y_2 </tex>.
}}
== Структура 2D Sparse Table ==
В целом структура 2D Sparse Table схожа со структурой обычной [[Решение_RMQ_с_помощью_разреженной_таблицы| разряженной таблице]]. Структура представляет собой четырехмерный массив <tex> ST[N][M][LOGN][LOGM], LOGN = \log(N), LOGM = \log(M) </tex>.
<tex>ST[i][j][k_1][k_2] = \min(A[i][j], A[i+1][j], \ldots, A[i+2^{k_1}-1][j] </tex>,
<tex>A[i][j + 1], A[i+1][j + 1], \ldots, A[i+2^{k_1}-1][j + 1], </tex>
<tex>\ldots \ldots\ldots\ldots\ldots</tex>,
<tex>A[i][j + 2^{k_2}-1], A[i+1][j + 2^{k_2}-1], \ldots, A[i+2^{k_1}-1][j + 2^{k_2}-1]),</tex> <tex> k_1 \in [0 \ldots \log N], k_2 \in [0 \ldots \log M] </tex>
То есть в ячейке структуры мы храним минимум для подматрицы, длины сторон которого являются некоторыми степенями двойки.
== Реализация 2D Sparse Table ==
'''Построение'''
Исходно полагаем, что все элементы структуры имеют значение <tex> inf </tex>.
Для начала необходимо присвоить элементам структуры, размеры которых <tex> 1 \times 1 </tex>, значения элементов исходной матрицы <tex> A </tex>.
'''for''' i : 1 to <tex> N </tex>
'''for''' j : 1 to <tex> M </tex>
<tex>ST[i][j][0][0] = A[i][j]</tex>
Далее мы считаем [[Решение_RMQ_с_помощью_разреженной_таблицы|1D Sparse Table]] для каждого столбца и строчки:
'''for''' lg : 1 to <tex> max(\log(N), \log(M)) </tex>
'''for''' i : 1 to <tex> N </tex>
'''for''' j : 1 to <tex> M </tex>
<tex>ST[i][j][lg][0] = min(ST[i][j][lg - 1][0], ST[i + 2^{lg}][j][lg - 1][0]);</tex>
<tex>ST[i][j][0][lg] = min(ST[i][j][0][lg - 1], ST[i][j+ 2^{lg}][0][lg - 1]);</tex>
Следующим шагом мы можем обновить значения для подматриц, так как для всех строк и столбцов ответы уже известны. Будем это делать по аналогичному алгоритму для 1D Sparse Table.
'''for''' <tex> k_1 </tex> : 1 to <tex> \log(N) </tex>
'''for''' <tex> k_2 </tex> : 1 to <tex> \log(M) </tex>
'''for''' i : 1 to <tex> N </tex>
'''for''' j : 1 to <tex> M </tex>
<tex>ST[i][j][k_1][k_2] = min(ST[i][j][k_1 - 1][k_2 - 1], ST[i + 2^{k_1}][j][k_1 - 1][k_2 - 1],</tex>
<tex>ST[i][j + 2^{k_2}][k_1 - 1][k_2 - 1], ST[i + 2^{k_1}][j + 2^{k_2}][k_1 - 1][k_2 - 1]) </tex>
Таким образом мы получили 2D Sparce Table за <tex>O(N * M * \log (N) * \log (M))</tex>
'''Ответы на запросы'''
Для ответа на запрос RMQ <tex> (l, r) </tex> в 1D Sparse Table использовалось пересечение отрезков <tex> [l, l + 2^{k}] </tex> и <tex> [r - 2^{k} + 1, r] </tex>, где <tex> k = \lfloor \log(SZ) \rfloor , SZ </tex> - размера массива для одномерной задачи.
Тут мы будем пользоваться аналогичным утверждением для матриц. Таким образов минимум на подматрице <tex>(x_1, y_1, x_2, y_2)</tex> будет высчитываться следующим образом:
<tex> k_1 = \lfloor \log(x_2 - x_1 + 1) \rfloor, k_2 = \lfloor \log(y_2 - y_1 + 1) \rfloor </tex>
<tex> ans = min(ST[x_1][y_1][k_1][k_2], ST[x_2 - 2^{k_1} + 1][y_1][k_1][k_2], </tex>
<tex> ST[x_1][y_2 - 2^{k_2} + 1][k_1][k_2], ST[x_2 - 2^{k_1} + 1][y_2 - 2^{k_2} + 1][k_1][k_2]) </tex>
Таким образом мы рассмотрим мы получаем ответ за <tex> O(1) </tex>, если предпосчитать логарифмы двоек, например так:
curLog = 0;
k = 1;
'''while ''' <tex> (k < max(N, M)) </tex>
lg[k] = curLog;
k = k * 2;
curLog = curLog + 1;
curLog = 0;
'''for''' k : 1 to <tex> max(N, M) </tex>
if (curLog != lg[k]) curLog = lg[k];
lg[k] = curLog;
----
При помощи 2D Sparse Table можно решать и некоторые другие задачи, например связанные с суммой на подматрице. ([[Решение_RMQ_с_помощью_разреженной_таблицы|Идемпотентность]])
== Источники информации==
[[Решение_RMQ_с_помощью_разреженной_таблицы| Идемпотентность]]
[[Категория: Алгоритмы и структуры данных]]
