112
правок
Изменения
First List Update
'''Двумерная разреженная таблица (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 <= \leq x_2 </tex> и <tex> y_1 <= \leq y_2 </tex> , для каждого из которых требуется найти минимум среди <tex>A[i][j], x_1 <= \leq i <= \leq x_2 </tex> и <tex> y_1 <= \leq j <= \leq y_2 </tex>.
}}
== Структура 2D Sparse Table ==
В целом структура 2D Sparse Table схожа со структурой обычной [[Решение_RMQ_с_помощью_разреженной_таблицы| разряженной таблице]]. Структура Разреженная таблица представляет собой четырехмерный массив :<tex> ST[N][M][LOGN][LOGM]</tex>, где <tex>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>,
== Реализация 2D Sparse Table ==
Исходно полагаем, что все элементы структуры имеют значение <tex> inf \infty</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 * NM\log (N) * \log (M))</tex>
Для ответа на запрос RMQ <tex> \mathrm {RMQ(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>
curLog = 0;
k = 1;
'''while ''' <tex> (k < \max(N, M)) </tex>
lg[k] = curLog;
k = k * 2;
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_с_помощью_разреженной_таблицы| Решение RMQ с помощью разреженной таблицы]]
[[Категория: Алгоритмы и структуры данных]]
