112
правок
Изменения
Нет описания правки
'''Двумерная разреженная таблица ''' (англ. ''2D Sparse Table)''' ) {{---}} структура данных, которая позволяет решать задачу online static RMQ.
{{Задача
== Структура 2D Sparse Table ==
В целом структура 2D Sparse Table схожа со структурой обычной [[Решение_RMQ_с_помощью_разреженной_таблицы| разряженной таблицеразреженной таблицы]].
Разреженная таблица представляет собой четырехмерный массив:
<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>
То есть в ячейке структуры мы храним минимум для подматрицы, длины сторон которого являются некоторыми степенями двойки.
[[Файл:STP1.png|left]]
[[Файл:SparseTableExample1Picture.png|right]]
Рассмотрим иллюстрации.
Слева изображен общий случай. Пусть n + 1 {{---}} количество строк, m + 1 {{---}} количество столбцов массива A. Рассмотрим элемент на позиции (i, j), который выделен желтым цветом. Данный элемент является левым верхним углом прямоугольника, стороны которого равны <tex>2^{k_1}</tex> и <tex>2^{k_2}</tex>. Прямоугольна выделен красным, а проекции его сторон - зеленым. Тогда в <tex>ST[i][j][k_1][k_2]</tex> будет хранится минимум из всех элементов, которые входят в красную и желтую область.
Справа изображен частный случай, когда N = 11, M = 11. Посмотрим, что будет хранится в ST[2][1][2][3]:
Клетка (2, 1), которая выделена желтым цветом, является левым верхним углом красного прямоугольника, длины сторон которого <tex>2^{2}</tex> и <tex>2^{3}</tex> (проекции этих сторон выделены зеленым цветом). И по определению выше, ST[2][1][3][2] хранит минимум из элементов красной области.
== Реализация 2D Sparse Table ==
===Построение===
Далее мы считаем [[Решение_RMQ_с_помощью_разреженной_таблицы|1D Sparse Tableодномерную разреженную таблицу]] для каждого столбца и строчки: '''for''' lg <tex> i = 1 </tex> '''to''' <tex> \max(\log(N), \log(M)) </tex> '''for''' i <tex> j = 1 </tex> '''to''' <tex> N M </tex> '''for''' j <tex> lg = 1 </tex> '''to''' <tex> M </tex> <tex>ST[i][j][lg][0] = \minlog(ST[i][j][lg - 1][0], ST[i + 2^{lg}][j][lg - 1][0]N)</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 = 1 </tex> = 1 '''to''' <tex> \log(N) </tex> '''for''' <tex> k_2 i = 1 </tex> = 1 '''to''' <tex> \log(M) N </tex> '''for''' i <tex> k_2 = 1 </tex> '''to''' <tex> N \log(M) </tex> '''for''' <tex> j = 1 </tex> '''to''' <tex> M </tex> <tex>ST[i][j][k_1][k_2] = \min\left(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]\right) </tex>
Таким образом мы получили 2D Sparce Table двумерную разреженную таблицу за <tex>O(NM\log(N)\log(M))</tex>
===Ответы на запросы===
Для ответа на запрос <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, </tex> <tex> k_2 = \lfloor \log(y_2 - y_1 + 1) \rfloor </tex> <tex> ans ans_1 = \min(ST[x_1][y_1][k_1][k_2], </tex> <span style="color:#008000"> // красный прямоугольник <tex> ans_2 = ST[x_2 - 2^{k_1} + 1][y_1][k_1][k_2], </tex><span style="color:#008000"> // Y-прямоугольник <tex> ans_3 = ST[x_1][y_2 - 2^{k_2} + 1][k_1][k_2], </tex> <span style="color:#008000"> // AA-прямоугольник <tex> ans_4 = ST[x_2 - 2^{k_1} + 1][y_2 - 2^{k_2} + 1][k_1][k_2]</tex> <span style="color:#008000"> // белый прямоугольник <tex> ans = \min\left(ans_1, ans_2, ans_3, ans_4\right) </tex>
[[Файл:ST3.png|center]] Таким образом мы рассмотрим мы получаем ответ на запрос <tex> \mathrm {RMQ(x_1, y_1, x_2, y_2)} </tex> за <tex> O(1) </tex>, если предпосчитать логарифмы двоек, например так: curLog <tex> lg[1] = 0; k = 1;</tex> '''while for''' (<tex>k</tex> <tex><i = 2 </tex> '''to''' <tex>\max\left(N, M\right)</tex>) <tex> lg[ki] = curLog; k = k * lg[i / 2; curLog = curLog ] + 1;</tex> curLog = 0;== Обобщение на большие размерности === '''for''' k = 1 '''to''' Можно заметить, что возможно реализовать и D-мерную разреженную таблицу за <tex> O((N\maxlog(n))^{D})</tex> памяти и <tex>O((N\log(n))^{D})</tex> времени на построение, где ответ на запрос, например, <tex> \mathrm {RMQ(l, Mr) } </tex> '''if''' будет выполняться за <tex> O(curLog != lg[k]D) curLog = lg[k]; lg[k] = curLog;</tex>.
''Способ построение'': Если в данном случае, для того, чтобы построить двумерную структуру мы сначала должны были построить одномерную, то также и в случае с D-мерной структуре - сначала нужно построить (D-1)-мерную, а из нее получить D-мерную, поэтому и получаем такую асимптотику на построение.
''Ответ на запрос'': Абсолютно аналогичен рассмотренному здесь, только обобщается до размерности D.
----
При помощи 2D Sparse Table можно решать и некоторые другие задачи, например, поиск суммы на подматрице. ([[Решение_RMQ_с_помощью_разреженной_таблицы|Идемпотентность]])
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]
