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

Двумерная разреженная таблица (англ. 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 \leqslant x_2 [/math] и [math] y_1 \leqslant y_2 [/math] , для каждого из которых требуется найти минимум среди [math]A[i][j], x_1 \leqslant i \leqslant x_2 [/math] и [math] y_1 \leqslant j \leqslant y_2 [/math].

Структура 2D Sparse Table

В целом структура 2D Sparse Table схожа со структурой обычной разреженной таблицы.

Разреженная таблица представляет собой четырехмерный массив: [math]ST[N][M][LOGN][LOGM][/math], где [math]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]

То есть в ячейке структуры мы храним минимум для подматрицы, длины сторон которого являются некоторыми степенями двойки.

Рассмотрим иллюстрации.

Слева изображен общий случай. Пусть n + 1 — количество строк, m + 1 — количество столбцов массива A. Рассмотрим элемент на позиции (i, j), который выделен желтым цветом. Данный элемент является левым верхним углом прямоугольника, стороны которого равны [math]2^{k_1}[/math] и [math]2^{k_2}[/math]. Прямоугольна выделен красным, а проекции его сторон - зеленым. Тогда в [math]ST[i][j][k_1][k_2][/math] будет хранится минимум из всех элементов, которые входят в красную и желтую область.

Справа изображен частный случай, когда N = 11, M = 11. Посмотрим, что будет хранится в ST[2][1][2][3]: Клетка (2, 1), которая выделена желтым цветом, является левым верхним углом красного прямоугольника, длины сторон которого [math]2^{2}[/math] и [math]2^{3}[/math] (проекции этих сторон выделены зеленым цветом). И по определению выше, ST[2][1][3][2] хранит минимум из элементов красной области.

Реализация 2D Sparse Table

Построение

Изначально заполним таблицу следующим образом:

<wikitex>$$ST[i][j][k_1][k_2]= \begin{cases} \infty ,&\text{если $k_1\neq0 \lor k_2\neq0$ ;}\\ A[i][j], &\text {если $k_1=0 \wedge k_2=0$ ;} \end{cases} $$ </wikitex>

Далее мы считаем одномерную разреженную таблицу для каждого столбца:

for [math] i = 1 [/math] to [math] N [/math]
    for [math] j = 1 [/math] to [math] M [/math]
        for [math] lg = 1 [/math] to [math] \log(N) [/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 = 1 [/math] to [math] \log(N) [/math]
    for [math] i = 1 [/math] to [math] N [/math]
        for [math] k_2 = 1 [/math] to [math] \log(M) [/math]
            for [math] j = 1 [/math] to [math] M [/math]         
                [math]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][k_2]\right)[/math]

Таким образом мы получили двумерную разреженную таблицу за [math]O(NM\log(N)\log(M))[/math]

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

Для ответа на запрос [math] \mathrm {RMQ(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 [/math]
[math] k_2 = \lfloor  \log(y_2 - y_1 + 1) \rfloor [/math]
[math] ans_1 = ST[x_1][y_1][k_1][k_2] [/math]      // красный прямоугольник
[math] ans_2 = ST[x_2 - 2^{k_1} + 1][y_1][k_1][k_2] [/math]      // Y-прямоугольник
[math] ans_3 = ST[x_1][y_2 - 2^{k_2} + 1][k_1][k_2] [/math]      // AA-прямоугольник
[math] ans_4 = ST[x_2 - 2^{k_1} + 1][y_2 - 2^{k_2} + 1][k_1][k_2] [/math]      // белый прямоугольник
[math] ans = \min\left(ans_1, ans_2, ans_3, ans_4\right) [/math] 

Таким образом мы получаем ответ на запрос [math] \mathrm {RMQ(x_1, y_1, x_2, y_2)} [/math] за [math] O(1) [/math], если предпосчитать логарифмы двоек, например так:

[math] lg[1] = 0 [/math]
for [math] i = 2 [/math] to [math]\max\left(N, M\right)[/math]
    [math] lg[i] = lg[i / 2] + 1 [/math]

Обобщение на большие размерности

Можно заметить, что возможно реализовать и D-мерную разреженную таблицу за [math]O((N\log(n))^{D})[/math] памяти и [math]O((N\log(n))^{D})[/math] времени на построение, где ответ на запрос, например, [math] \mathrm {RMQ(l, r)} [/math] будет выполняться за [math] O(D) [/math].

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

Ответ на запрос: Абсолютно аналогичен рассмотренному здесь, только обобщается до размерности D.

---

При помощи 2D Sparse Table можно решать и некоторые другие задачи, например, поиск суммы на подматрице. (Идемпотентность)

См. также

• Решение RMQ с помощью разреженной таблицы