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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показано 12 промежуточных версий 10 участников)
Строка 21: Строка 21:
 
Рассмотрим иллюстрации.
 
Рассмотрим иллюстрации.
  
Слева изображен общий случай. Пусть n + 1 {{---}} количество строк, m + 1 {{---}} количество столбцов массива A. Рассмотрим элемент на позиции (i, j), который выделен желтым цветом. Данный элемент является левым верхним углом прямоугольника, стороны которого равны <tex>2^{k_1}</tex> и <tex>2^{k_2}</tex>. Прямоугольна выделен красным, а проекции его сторон - зеленым. Тогда в <tex>ST[i][j][k_1][k_2]</tex> будет хранится минимум из всех элементов, которые входят в красную и желтую область.
+
Слева изображен общий случай. Пусть <tex>n + 1</tex> {{---}} количество строк, <tex>m + 1</tex> {{---}} количество столбцов массива A. Рассмотрим элемент на позиции <tex>(i, j)</tex>, который выделен желтым цветом. Данный элемент является левым верхним углом прямоугольника, стороны которого равны <tex>2^{k_1}</tex> и <tex>2^{k_2}</tex>. Прямоугольна выделен красным, а проекции его сторон - зеленым. Тогда в <tex>ST[i][j][k_1][k_2]</tex> будет храниться минимум из всех элементов, которые входят в красную и желтую область.
 
 
Справа изображен частный случай, когда N = 11, M = 11. Посмотрим, что будет хранится в ST[2][1][2][3]:
 
Клетка (2, 1), которая выделена желтым цветом, является левым верхним углом красного прямоугольника, длины сторон которого <tex>2^{2}</tex> и <tex>2^{3}</tex> (проекции этих сторон выделены зеленым цветом). И по определению выше, ST[2][1][3][2] хранит минимум из элементов красной области.
 
  
 +
Справа изображен частный случай, когда N = 11, M = 11. Посмотрим, что будет храниться в <tex>ST[2][1][2][3]</tex>:
 +
Клетка (2, 1), которая выделена желтым цветом, является левым верхним углом красного прямоугольника, длины сторон которого <tex>2^{2}</tex> и <tex>2^{3}</tex> (проекции этих сторон выделены зеленым цветом). И по определению выше, <tex>ST[2][1][3][2]</tex> хранит минимум из элементов красной области.
  
 
== Реализация 2D Sparse Table ==
 
== Реализация 2D Sparse Table ==
Строка 33: Строка 32:
 
Изначально заполним таблицу следующим образом:
 
Изначально заполним таблицу следующим образом:
  
<wikitex>$$ST[i][j][k_1][k_2]=
+
$$ST[i][j][k_1][k_2]=
 
\begin{cases}
 
\begin{cases}
 
\infty ,&\text{если $k_1\neq0 \lor k_2\neq0$ ;}\\
 
\infty ,&\text{если $k_1\neq0 \lor k_2\neq0$ ;}\\
Строка 39: Строка 38:
 
\end{cases}
 
\end{cases}
 
$$
 
$$
</wikitex>
 
  
 
Далее мы считаем [[Решение_RMQ_с_помощью_разреженной_таблицы|одномерную разреженную таблицу]] для каждого столбца:
 
Далее мы считаем [[Решение_RMQ_с_помощью_разреженной_таблицы|одномерную разреженную таблицу]] для каждого столбца:
  '''for''' <tex> i = 1 </tex> '''to''' <tex> N </tex>
+
  '''for''' <tex> i = 0 </tex> '''to''' <tex> N </tex>
     '''for''' <tex> j = 1 </tex> '''to''' <tex> M </tex>
+
     '''for''' <tex> lg = 1 </tex> '''to''' <tex> \log(M) </tex>        
         '''for''' <tex> lg = 1 </tex> '''to''' <tex> \log(N) </tex>        
+
         '''for''' <tex> j = 0 </tex> '''to''' <tex> M </tex>  
             <tex>ST[i][j][0][lg] = \min(ST[i][j][0][lg - 1], ST[i][j+ 2^{lg}][0][lg - 1])</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.
 
Следующим шагом мы можем обновить значения для подматриц, так как для всех столбцов ответы уже известны. Будем это делать по аналогичному алгоритму для 1D Sparse Table.
 
  '''for''' <tex> k_1 = 1 </tex> '''to''' <tex> \log(N) </tex>
 
  '''for''' <tex> k_1 = 1 </tex> '''to''' <tex> \log(N) </tex>
     '''for''' <tex> i = 1 </tex> '''to''' <tex> N </tex>
+
     '''for''' <tex> i = 0 </tex> '''to''' <tex> N </tex>
         '''for''' <tex> k_2 = 1 </tex> '''to''' <tex> \log(M) </tex>
+
         '''for''' <tex> k_2 = 0 </tex> '''to''' <tex> \log(M) </tex>
             '''for''' <tex> j = 1 </tex> '''to''' <tex> M </tex>         
+
             '''for''' <tex> j = 0 </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>
 
                 <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>
  
Строка 78: Строка 76:
 
=== Обобщение на большие размерности ===
 
=== Обобщение на большие размерности ===
  
Можно заметить, что возможно реализовать и D-мерную разреженную таблицу за <tex>O((N\log(n))^{D})</tex> памяти и <tex>O((N\log(n))^{D})</tex> времени на построение, где ответ на запрос, например, <tex> \mathrm {RMQ(l, r)} </tex> будет выполняться за <tex> O(D) </tex>.
+
Можно заметить, что возможно реализовать и D-мерную разреженную таблицу за <tex>O((N\log(n))^{D})</tex> памяти и <tex>O((N\log(n))^{D})</tex> времени на построение, где ответ на запрос, например, <tex> \mathrm {RMQ(l, r)} </tex> будет выполняться за <tex> O(2^{D}) </tex>.
  
''Способ построение'': Если в данном случае, для того, чтобы построить двумерную структуру мы сначала должны были построить одномерную, то также и в случае с D-мерной структуре - сначала нужно построить (D-1)-мерную, а из нее получить D-мерную, поэтому и получаем такую асимптотику на построение.
+
''Способ построения'': Если в данном случае, для того, чтобы построить двумерную структуру мы сначала должны были построить одномерную, то также и в случае с D-мерной структуре - сначала нужно построить (D-1)-мерную, а из нее получить D-мерную.
  
 
''Ответ на запрос'': Абсолютно аналогичен рассмотренному здесь, только обобщается до размерности D.
 
''Ответ на запрос'': Абсолютно аналогичен рассмотренному здесь, только обобщается до размерности D.
 
----
 
При помощи 2D Sparse Table можно решать и некоторые другие задачи, например, поиск суммы, произведения элементов подматрицы.
 
  
 
== См. также ==
 
== См. также ==

Текущая версия на 19:37, 4 сентября 2022

Двумерная разреженная таблица (англ. 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\limits_{r = i,\dots,i+2^{k_1}-1, c = j,\ldots,j + 2^{k_2}-1} A[r][c], r \lt N, c \lt M [/math]

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

STP1.png
SparseTableExample1Picture.png

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

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

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

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

Построение

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

$$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} $$

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

for [math] i = 0 [/math] to [math] N [/math]
    for [math] lg = 1 [/math] to [math] \log(M) [/math]         
        for [math] j = 0 [/math] to [math] M [/math]   
            [math]ST[i][j][0][lg] = \min(ST[i][j][0][lg - 1], ST[i][j+ 2^{lg-1}][0][lg - 1])[/math]

Следующим шагом мы можем обновить значения для подматриц, так как для всех столбцов ответы уже известны. Будем это делать по аналогичному алгоритму для 1D Sparse Table.

for [math] k_1 = 1 [/math] to [math] \log(N) [/math]
    for [math] i = 0 [/math] to [math] N [/math]
        for [math] k_2 = 0 [/math] to [math] \log(M) [/math]
            for [math] j = 0 [/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 - 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] 
ST3.png

Таким образом мы получаем ответ на запрос [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(2^{D}) [/math].

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

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

См. также