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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (переименовал Участник:Alex PKZDL в 2D Sparse Table: Неправильное название)
м (rollbackEdits.php mass rollback)
 
(не показана 21 промежуточная версия 11 участников)
Строка 1: Строка 1:
'''2D Sparse Table''' - это структура данных, которая позволяет решать задачу online static RMQ.  
+
'''Двумерная разреженная таблица''' (англ. ''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 <= x_2 </tex> и <tex> y_1 <= y_2 </tex> , для каждого из которых требуется найти минимум среди <tex>A[i][j], x_1 <= i <= x_2 </tex> и <tex> y_1 <= j <= y_2 </tex>.
+
|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 ==
 
== Структура 2D Sparse Table ==
  
В целом структура 2D Sparse Table схожа со структурой обычной [[Решение_RMQ_с_помощью_разреженной_таблицы| разряженной таблице]]. Структура представляет собой четырехмерный массив <tex> ST[N][M][LOGN][LOGM], LOGN = \log(N), LOGM = \log(M) </tex>.
+
В целом структура 2D Sparse Table схожа со структурой обычной [[Решение_RMQ_с_помощью_разреженной_таблицы| разреженной таблицы]].  
  
<tex>ST[i][j][k_1][k_2] = \min(A[i][j], A[i+1][j], \ldots, A[i+2^{k_1}-1][j] </tex>,
+
Разреженная таблица представляет собой четырехмерный массив:
                        <tex>A[i][j + 1], A[i+1][j + 1], \ldots, A[i+2^{k_1}-1][j + 1], </tex>
+
<tex>ST[N][M][LOGN][LOGM]</tex>, где <tex>LOGN = \log(N), LOGM = \log(M)</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}-1][j + 2^{k_2}-1]),</tex> <tex> k_1 \in [0 \ldots \log N], k_2 \in [0 \ldots \log M] </tex>
+
<tex> 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 < N, c < M </tex>
 +
 
То есть в ячейке структуры мы храним минимум для подматрицы, длины сторон которого являются некоторыми степенями двойки.
 
То есть в ячейке структуры мы храним минимум для подматрицы, длины сторон которого являются некоторыми степенями двойки.
 +
 +
[[Файл:STP1.png|left]]
 +
[[Файл:SparseTableExample1Picture.png|right]]
 +
 +
Рассмотрим иллюстрации.
 +
 +
Слева изображен общий случай. Пусть <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. Посмотрим, что будет храниться в <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 ==
  
'''Построение'''
+
===Построение===
  
Исходно полагаем, что все элементы структуры имеют значение <tex> inf </tex>.
+
Изначально заполним таблицу следующим образом:
  
Для начала необходимо присвоить элементам структуры, размеры которых <tex> 1 \times 1 </tex>, значения элементов исходной матрицы <tex> A </tex>.
+
$$ST[i][j][k_1][k_2]=
'''for''' i : 1 to <tex> N </tex>
+
\begin{cases}
    '''for''' j : 1 to <tex> M </tex>
+
\infty ,&\text{если $k_1\neq0 \lor k_2\neq0$ ;}\\
        <tex>ST[i][j][0][0] = A[i][j]</tex>
+
A[i][j], &\text {если $k_1=0 \wedge k_2=0$ ;}
 +
\end{cases}
 +
$$
  
Далее мы считаем [[Решение_RMQ_с_помощью_разреженной_таблицы|1D Sparse Table]] для каждого столбца и строчки:
+
Далее мы считаем [[Решение_RMQ_с_помощью_разреженной_таблицы|одномерную разреженную таблицу]] для каждого столбца:
  '''for''' lg : 1 to <tex> max(\log(N), \log(M)) </tex>
+
  '''for''' <tex> i = 0 </tex> '''to''' <tex> N </tex>
     '''for''' i : 1 to <tex> N </tex>
+
     '''for''' <tex> lg = 1 </tex> '''to''' <tex> \log(M) </tex>         
        '''for''' j : 1 to <tex> M </tex>         
+
        '''for''' <tex> j = 0 </tex> '''to''' <tex> M </tex> 
            <tex>ST[i][j][lg][0] = min(ST[i][j][lg - 1][0], ST[i + 2^{lg}][j][lg - 1][0]);</tex>
+
             <tex>ST[i][j][0][lg] = \min(ST[i][j][0][lg - 1], ST[i][j+ 2^{lg-1}][0][lg - 1])</tex>
             <tex>ST[i][j][0][lg] = min(ST[i][j][0][lg - 1], ST[i][j+ 2^{lg}][0][lg - 1]);</tex>
 
  
Следующим шагом мы можем обновить значения для подматриц, так как для всех строк и столбцов ответы уже известны. Будем это делать по аналогичному алгоритму для 1D Sparse Table.
+
Следующим шагом мы можем обновить значения для подматриц, так как для всех столбцов ответы уже известны. Будем это делать по аналогичному алгоритму для 1D Sparse Table.
  '''for''' <tex> k_1 </tex> : 1 to <tex> \log(N) </tex>
+
  '''for''' <tex> k_1 = 1 </tex> '''to''' <tex> \log(N) </tex>
     '''for''' <tex> k_2 </tex> : 1 to <tex> \log(M) </tex>
+
     '''for''' <tex> i = 0 </tex> '''to''' <tex> N </tex>
         '''for''' i : 1 to <tex> N </tex>
+
         '''for''' <tex> k_2 = 0 </tex> '''to''' <tex> \log(M) </tex>
             '''for''' j : 1 to <tex> M </tex>         
+
             '''for''' <tex> j = 0 </tex> '''to''' <tex> M </tex>         
            <tex>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],</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 + 2^{k_2}][k_1 - 1][k_2 - 1],  ST[i + 2^{k_1}][j + 2^{k_2}][k_1 - 1][k_2 - 1]) </tex>
 
  
Таким образом мы получили 2D Sparce Table за <tex>O(N * M * \log (N) * \log (M))</tex>
+
Таким образом мы получили двумерную разреженную таблицу за <tex>O(NM\log(N)\log(M))</tex>
  
'''Ответы на запросы'''
+
===Ответы на запросы===
  
Для ответа на запрос RMQ <tex> (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> \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>(x_1, y_1, x_2, y_2)</tex> будет высчитываться следующим образом:
 
Тут мы будем пользоваться аналогичным утверждением для матриц. Таким образов минимум на подматрице  <tex>(x_1, y_1, x_2, y_2)</tex> будет высчитываться следующим образом:
  <tex> k_1 = \lfloor  \log(x_2 - x_1 + 1) \rfloor, k_2 = \lfloor  \log(y_2 - y_1 + 1) \rfloor </tex>
+
  <tex> k_1 = \lfloor  \log(x_2 - x_1 + 1) \rfloor </tex>
  <tex> ans = min(ST[x_1][y_1][k_1][k_2], ST[x_2 - 2^{k_1} + 1][y_1][k_1][k_2], </tex>
+
<tex> k_2 = \lfloor  \log(y_2 - y_1 + 1) \rfloor </tex>
            <tex> 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]) </tex>
+
  <tex> ans_1 = 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-мерную разреженную таблицу за <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-мерную.
  
При помощи 2D Sparse Table можно решать и некоторые другие задачи, например связанные с суммой на подматрице. ([[Решение_RMQ_с_помощью_разреженной_таблицы|Идемпотентность]])
+
''Ответ на запрос'': Абсолютно аналогичен рассмотренному здесь, только обобщается до размерности D.
  
== Источники информации==
+
== См. также ==
[[Решение_RMQ_с_помощью_разреженной_таблицы| Идемпотентность]]
+
* [[Решение_RMQ_с_помощью_разреженной_таблицы| Решение RMQ с помощью разреженной таблицы]]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Задача о наименьшем общем предке]]

Текущая версия на 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.

См. также