Изменения

'''Двумерная разреженная таблица''' (англ. ''2D Sparse Table''' ) {{--- это }} структура данных, которая позволяет решать задачу online static RMQ.

|definition = Дан двумерный массив <tex>A[1 \ldots N][1 \ldots M]</tex> целых чисел. Поступают запросы вида <tex>(x_1, y_1, x_2, y_2)</tex> такие, что <tex> x_1 <= \leqslant x_2 </tex> и <tex> y_1 <= \leqslant y_2 </tex> , для каждого из которых требуется найти минимум среди <tex>A[i][j], x_1 <= \leqslant i <= \leqslant x_2 </tex> и <tex> y_1 <= \leqslant j <= \leqslant y_2 </tex>.

В целом структура 2D Sparse Table схожа со структурой обычной [[Решение_RMQ_с_помощью_разреженной_таблицы| разряженной таблицеразреженной таблицы]]. Структура представляет собой четырехмерный массив <tex> ST[N][M][LOGN][LOGM], LOGN = \log(N), LOGM = \log(M) </tex>.

Разреженная таблица представляет собой четырехмерный массив:<tex>ST[iN][jM][k_1LOGN][k_2LOGM] </tex>, где <tex>LOGN = \minlog(A[i][j], A[i+1][j]N), LOGM = \ldots, A[i+2^{k_1}-1][j] log(M)</tex>,. <tex>AST[i][j + 1], A[i+1k_1][j + 1k_2]= \min\limits_{r = i, \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>

'''===Построение'''===

Для начала необходимо присвоить элементам структуры, размеры которых <tex> 1 \times 1 </tex>, значения элементов исходной матрицы <tex> A </tex>. '''for''' i : 1 to <tex> N </tex> '''for''' j : 1 to <tex> M </tex> <tex>$$ST[i][j][0k_1][0k_2] = \begin{cases}\infty ,&\text{если $k_1\neq0 \lor k_2\neq0$ ;}\\A[i][j]</tex>, &\text {если $k_1=0 \wedge k_2=0$ ;}\end{cases}$$

Далее мы считаем [[Решение_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 : 1 to <tex> M lg = 1 </tex> '''to''' <tex>ST[i][j][lg][0] = min\log(ST[i][j][lg - 1][0], ST[i + 2^{lg}][j][lg - 1][0]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> : 1 '''to ''' <tex> \log(N) </tex> '''for''' <tex> k_2 i = 1 </tex> : 1 '''to ''' <tex> \log(M) N </tex> '''for''' i : 1 <tex> k_2 = 0 </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(N * M * NM\log (N) * \log (M))</tex>

'''===Ответы на запросы'''===

Для ответа на запрос RMQ <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> 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>, если предпосчитать логарифмы двоек, например так: <tex> lg[1] = 0 </tex> '''for''' <tex> i = 2 </tex> '''to''' <tex>\max\left(N, M\right) </tex> <tex> lg[i] = lg[i / 2] + 1 </tex>

Таким образом мы рассмотрим мы получаем ответ за <tex> O(1) </tex>, если предпосчитать логарифмы двоек, например так: curLog = 0; k = 1; '''while ''' <tex> (k < max(N, M)) </tex> lg[k] = curLog; k Обобщение на большие размерности = k * 2; curLog = curLog + 1; curLog = 0; '''for''' k : 1 to <tex> max(N, M) </tex> if (curLog != lg[k]) curLog = lg[k]; lg[k] = curLog;

''Способ построения'': Если в данном случае, для того, чтобы построить двумерную структуру мы сначала должны были построить одномерную, то также и в случае с D-мерной структуре -сначала нужно построить (D-1)-мерную, а из нее получить D-мерную.

При помощи 2D Sparse Table можно решать и некоторые другие задачи''Ответ на запрос'': Абсолютно аналогичен рассмотренному здесь, например связанные с суммой на подматрицетолько обобщается до размерности D. ([[Решение_RMQ_с_помощью_разреженной_таблицы|Идемпотентность]])

== Источники информацииСм. также ==* [[Решение_RMQ_с_помощью_разреженной_таблицы| Решение RMQ с помощью разреженной таблицы]]