Изменения
На картинках отсчет матриц идет с нуля, а не с единицы. Можно также добавить, что нужно не выйти за верхние границы...
Далее мы считаем [[Решение_RMQ_с_помощью_разреженной_таблицы|одномерную разреженную таблицу]] для каждого столбца:
'''for''' <tex> i = 1 0 </tex> '''to''' <tex> N </tex> '''for''' <tex> j = 1 0 </tex> '''to''' <tex> M </tex>
'''for''' <tex> lg = 1 </tex> '''to''' <tex> \log(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 = 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>
