1632
правки
Изменения
м
<wikitex>$$ST[i][j][k_1][k_2]=
</wikitex>
rollbackEdits.php mass rollback
Рассмотрим иллюстрации.
Слева изображен общий случай. Пусть <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. Посмотрим, что будет хранится храниться в <tex>ST[2][1][2][3]</tex>:
Клетка (2, 1), которая выделена желтым цветом, является левым верхним углом красного прямоугольника, длины сторон которого <tex>2^{2}</tex> и <tex>2^{3}</tex> (проекции этих сторон выделены зеленым цветом). И по определению выше, <tex>ST[2][1][3][2]</tex> хранит минимум из элементов красной области.
Изначально заполним таблицу следующим образом:
\begin{cases}
\infty ,&\text{если $k_1\neq0 \lor k_2\neq0$ ;}\\
\end{cases}
$$
Далее мы считаем [[Решение_RMQ_с_помощью_разреженной_таблицы|одномерную разреженную таблицу]] для каждого столбца:
'''for''' <tex> i = 1 0 </tex> '''to''' <tex> N </tex> '''for''' <tex> j lg = 1 </tex> '''to''' <tex> \log(M ) </tex> '''for''' <tex> lg j = 1 0 </tex> '''to''' <tex> \log(N) M </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 0 </tex> '''to''' <tex> N </tex> '''for''' <tex> k_2 = 1 0 </tex> '''to''' <tex> \log(M) </tex> '''for''' <tex> j = 1 0 </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>
