2D Sparse Table - это структура данных, которая позволяет решать задачу online static RMQ.
| Задача: |
| Дан двумерный массив [math]A[1 \ldots N][1 \ldots M][/math] целых чисел. Поступают запросы вида [math](x_1, y_1, x_2, y_2)[/math] такие, что [math] x_1 \lt = x_2 [/math] и [math] y_1 \lt = y_2 [/math] , для каждого из которых требуется найти минимум среди [math]A[i][j], x_1 \lt = i \lt = x_2 [/math] и [math] y_1 \lt = j \lt = y_2 [/math]. |
Структура 2D Sparse Table
В целом структура 2D Sparse Table схожа со структурой обычной разряженной таблице. Структура представляет собой четырехмерный массив [math] ST[N][M][LOGN][LOGM], LOGN = \log(N), LOGM = \log(M) [/math].
[math]ST[i][j][k_1][k_2] = \min(A[i][j], A[i+1][j], \ldots, A[i+2^{k_1}-1][j] [/math],
[math]A[i][j + 1], A[i+1][j + 1], \ldots, A[i+2^{k_1}-1][j + 1], [/math]
[math]\ldots \ldots\ldots\ldots\ldots[/math],
[math]A[i][j + 2^{k_2}-1], A[i+1][j + 2^{k_2}-1], \ldots, A[i+2^{k_1}-1][j + 2^{k_2}-1]),[/math] [math] k_1 \in [0 \ldots \log N], k_2 \in [0 \ldots \log M] [/math]
То есть в ячейке структуры мы храним минимум для подматрицы, длины сторон которого являются некоторыми степенями двойки.
Реализация 2D Sparse Table
Построение
Исходно полагаем, что все элементы структуры имеют значение [math] inf [/math].
Для начала необходимо присвоить элементам структуры, размеры которых [math] 1 \times 1 [/math], значения элементов исходной матрицы [math] A [/math].
for i : 1 to [math] N [/math]
for j : 1 to [math] M [/math]
[math]ST[i][j][0][0] = A[i][j][/math]
Далее мы считаем 1D Sparse Table для каждого столбца и строчки:
for lg : 1 to [math] max(\log(N), \log(M)) [/math]
for i : 1 to [math] N [/math]
for j : 1 to [math] M [/math]
[math]ST[i][j][lg][0] = min(ST[i][j][lg - 1][0], ST[i + 2^{lg}][j][lg - 1][0]);[/math]
[math]ST[i][j][0][lg] = min(ST[i][j][0][lg - 1], ST[i][j+ 2^{lg}][0][lg - 1]);[/math]
Следующим шагом мы можем обновить значения для подматриц, так как для всех строк и столбцов ответы уже известны. Будем это делать по аналогичному алгоритму для 1D Sparse Table.
for [math] k_1 [/math] : 1 to [math] \log(N) [/math]
for [math] k_2 [/math] : 1 to [math] \log(M) [/math]
for i : 1 to [math] N [/math]
for j : 1 to [math] M [/math]
[math]ST[i][j][k_1][k_2] = min(ST[i][j][k_1 - 1][k_2 - 1], ST[i + 2^{k_1}][j][k_1 - 1][k_2 - 1],[/math]
[math]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]) [/math]
Таким образом мы получили 2D Sparce Table за [math]O(N * M * \log (N) * \log (M))[/math]
Ответы на запросы
Для ответа на запрос RMQ [math] (l, r) [/math] в 1D Sparse Table использовалось пересечение отрезков [math] [l, l + 2^{k}] [/math] и [math] [r - 2^{k} + 1, r] [/math], где [math] k = \lfloor \log(SZ) \rfloor , SZ [/math] - размера массива для одномерной задачи.
Тут мы будем пользоваться аналогичным утверждением для матриц. Таким образов минимум на подматрице [math](x_1, y_1, x_2, y_2)[/math] будет высчитываться следующим образом:
[math] k_1 = \lfloor \log(x_2 - x_1 + 1) \rfloor, k_2 = \lfloor \log(y_2 - y_1 + 1) \rfloor [/math]
[math] ans = min(ST[x_1][y_1][k_1][k_2], ST[x_2 - 2^{k_1} + 1][y_1][k_1][k_2], [/math]
[math] ST[x_1][y_2 - 2^{k_2} + 1][k_1][k_2], ST[x_2 - 2^{k_1} + 1][y_2 - 2^{k_2} + 1][k_1][k_2]) [/math]
Таким образом мы рассмотрим мы получаем ответ за [math] O(1) [/math], если предпосчитать логарифмы двоек, например так:
curLog = 0;
k = 1;
while [math] (k \lt max(N, M)) [/math]
lg[k] = curLog;
k = k * 2;
curLog = curLog + 1;
curLog = 0;
for k : 1 to [math] max(N, M) [/math]
if (curLog != lg[k]) curLog = lg[k];
lg[k] = curLog;
При помощи 2D Sparse Table можно решать и некоторые другие задачи, например связанные с суммой на подматрице. (Идемпотентность)
Источники информации
Решение RMQ с помощью разреженной таблицы
