24
правки
Изменения
м
<tex>ST[i][j][k_1][k_2] = \min(A[i][j], A[i+1][j], \ldots, A[i+2^limits_{k_1}-1][j] </tex>, <tex>A[r = i][j + 1], A[i+1][j + 1], \ldotsdots, A[i+2^{k_1}-1][, c = 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}-1r][j + 2^{k_2}-1c]),r </tex> <tex> k_1 \in [0 \ldots \log N], k_2 \in [0 \ldots \log c < M] </tex>
<wikitex>$$ST[i][j][k_1][k_2]=
</wikitex>
----
При помощи 2D Sparse Table можно решать и некоторые другие задачи, например, поиск суммы, произведение на элементов подматрицы.
2 правки орфографии
Разреженная таблица представляет собой четырехмерный массив:
<tex>ST[N][M][LOGN][LOGM]</tex>, где <tex>LOGN = \log(N), LOGM = \log(M)</tex>.
То есть в ячейке структуры мы храним минимум для подматрицы, длины сторон которого являются некоторыми степенями двойки.
Рассмотрим иллюстрации.
Слева изображен общий случай. Пусть <tex>n + 1 </tex> {{---}} количество строк, <tex>m + 1 </tex> {{---}} количество столбцов массива A. Рассмотрим элемент на позиции <tex>(i, j)</tex>, который выделен желтым цветом. Данный элемент является левым верхним углом прямоугольника, стороны которого равны <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] хранит минимум из элементов красной области.
Справа изображен частный случай, когда N = 11, M = 11. Посмотрим, что будет храниться в <tex>ST[2][1][2][3]</tex>:
Клетка (2, 1), которая выделена желтым цветом, является левым верхним углом красного прямоугольника, длины сторон которого <tex>2^{2}</tex> и <tex>2^{3}</tex> (проекции этих сторон выделены зеленым цветом). И по определению выше, <tex>ST[2][1][3][2]</tex> хранит минимум из элементов красной области.
== Реализация 2D Sparse Table ==
Изначально заполним таблицу следующим образом:
\begin{cases}
\infty ,&\text{если $k_1\neq0 \lor k_2\neq0$ ;}\\
\end{cases}
$$
Далее мы считаем [[Решение_RMQ_с_помощью_разреженной_таблицы|одномерную разреженную таблицу]] для каждого столбца:
'''for''' <tex> i = 1 </tex> '''to''' <tex> N </tex>
'''for''' <tex> j = 1 </tex> '''to''' <tex> M </tex>
'''for''' <tex> lg = 1 </tex> '''to''' <tex> \log(NM) </tex> <tex>ST[i][j][0][lg] = \min(ST[i][j][0][lg - 1], ST[i][j+ 2^{lg-1}][0][lg - 1])</tex>
Следующим шагом мы можем обновить значения для подматриц, так как для всех столбцов ответы уже известны. Будем это делать по аналогичному алгоритму для 1D Sparse Table.
'''for''' <tex> k_1 = 1 </tex> '''to''' <tex> \log(N) </tex>
'''for''' <tex> i = 1 </tex> '''to''' <tex> N </tex>
'''for''' <tex> k_2 = 1 0 </tex> '''to''' <tex> \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],ST[i+2^{k_1-1}][j][k_1- 1][k_2]\right)</tex>
Таким образом мы получили двумерную разреженную таблицу за <tex>O(NM\log(N)\log(M))</tex>
=== Обобщение на большие размерности ===
Можно заметить, что возможно реализовать и D-мерную разреженную таблицу за <tex>O((N\log(n))^{D})</tex> памяти и <tex>O((N\log(n))^{D})</tex> времени на построение, где ответ на запрос, например, <tex> \mathrm {RMQ(l, r)} </tex> будет выполняться за <tex> O(2^{D}) </tex>.
''Способ построениепостроения'': Если в данном случае, для того, чтобы построить двумерную структуру мы сначала должны были построить одномерную, то также и в случае с D-мерной структуре - сначала нужно построить (D-1)-мерную, а из нее получить D-мерную, поэтому и получаем такую асимптотику на построение.
''Ответ на запрос'': Абсолютно аналогичен рассмотренному здесь, только обобщается до размерности D.
== См. также ==
