Изменения

Перейти к: навигация, поиск

Двумерная разреженная таблица

Нет изменений в размере, 25 май
Построение
'''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>
'''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>
Анонимный участник

Навигация