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

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 с помощью разреженной таблицы