Сжатое многомерное дерево отрезков — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Структура)
м (rollbackEdits.php mass rollback)
 
(не показано 78 промежуточных версий 6 участников)
Строка 1: Строка 1:
{{В разработке}}
+
{{Задача
 
 
{{Определение
 
 
|definition=
 
|definition=
Пусть дан <tex>p</tex>-мерный массив и множество <tex>A</tex>, состоящее из <tex>n</tex> его элементов.'''<br>Сжатым <tex>p</tex>-мерным деревом отрезков''' называется модификация <tex>p</tex>-мерного дерева отрезков, позволяющая реализовывать моноидальные операции (нахождение количества элементов, минимального элемента, etc) над элементами множества <tex>A</tex>, принадлежащими <tex>p</tex>-мерному подмассиву <tex>(x_a,x_b),(y_a,y_b),...,(z_a,z_b)</tex>.
+
Пусть имеется множество <tex>A</tex>, состоящее из <tex>n</tex> взвешенных точек в <tex>p</tex>-мерном пространстве. Необходимо быстро отвечать на запрос о суммарном весе точек, находящихся в <tex>p</tex>-мерном прямоугольнике <tex>(x_a,x_b),(y_a,y_b),\dots,(z_a,z_b)</tex>
 
}}
 
}}
Важно понимать, что индексы p-мерного массива вполне могут быть заменены координатами в p-мерном вещественном пространстве. Тогда для определения нужного отрезка необходимо будет воспользоваться бинарным поиском. Например, сжатое дерево отрезков решает следующую задачу: заданы <tex>n</tex> точек на плоскости с координатами <tex>(x_i,y_i)</tex>, посчитать количество точек на прямоугольнике <tex>(x_a,x_b),(y_a,y_b)</tex>.
+
Вообще говоря, с поставленной задачей справится и [[Многомерное дерево отрезков|обычное <tex>p</tex>-мерное дерево отрезков]]. Для этого достаточно на <tex>i</tex>-том уровне вложенности строить дерево отрезков по всевозможным <tex>i</tex>-тым координатам точек множества <tex>A</tex>, а при запросе использовать на каждом уровне бинарный поиск для установления желаемого подотрезка. Очевидно, запрос будет делаться за <tex>O(\log^p\,n)</tex> времени, а сама структура данных будет занимать <tex>O(n^p)</tex> памяти.
 +
 
 +
==Оптимизация==
 +
Для уменьшения количества занимаемой памяти можно провести оптимизацию <tex>p</tex>-мерного дерева отрезков. Для начала, будем использовать дерево отрезков с сохранением всего подотрезка в каждой вершине. Другими словами, в каждой вершине дерева отрезков мы будем хранить не только какую-то сжатую информацию об этом подотрезке, но и все элементы множества <tex>A</tex>, лежащие в этом подотрезке. На первый взгляд, это только увеличит объем структуры, но не все так просто. При построении будем действовать следующим образом — каждый раз дерево отрезков внутри вершины будем строить не по всем элементам множества <tex>A</tex>, а только по сохраненному в этой вершине подотрезку. Действительно, незачем строить дерево по всем элементам, когда элементы вне подотрезка уже были «исключены»  и заведомо лежат вне желаемого <tex>p</tex>-мерного прямоугольника. Такое «усеченное»  многомерное дерево отрезков называется '''сжатым''' (англ. ''compressed'').
 +
 
 +
==Построение дерева==
 +
Рассмотрим алгоритм построения сжатого дерева отрезков на примере множества <tex>A</tex>, состоящего из <tex>4</tex>-х взвешенных точек в <tex>2</tex>-мерном пространстве (плоскости):<br>
  
==Структура==
+
<tex>
Вообще говоря, с поставленной задачей справится и обычное <tex>p</tex>-мерное дерево отрезков.  Очевидно, запрос операции на <tex>p</tex>-мерном прямоугольнике c помощью такой структуры будет выполняться за <tex>O(log^p\,n)</tex>, а сама структура будет занимать или порядка <tex>\Omega(S)</tex> памяти, где <tex>S</tex> — количество элементов в <tex>p</tex>-мерном массиве, или порядка <tex>O(n^p)</tex> памяти — зависит от построения. Однако, можно провести следующую оптимизацию — каждый раз дерево отрезков внутри вершины будем строить только по тем элементам, которые встречаются в отрезке, за который отвечает эта вершина. Действительно, другие элементы уже были "исключены" и заведомо лежат вне желаемого <tex>p</tex>-мерного прямоугольника. Для этого будем использовать сохранение всего подмассива в каждой вершине дерева отрезков.
+
p=2,~~n=4,~~A:
 +
\begin{cases}
 +
(1, 3), \mbox{weight}=7 \\
 +
(2, 1), \mbox{weight}=1 \\
 +
(3, 3), \mbox{weight}=8 \\
 +
(4, 2), \mbox{weight}=5
 +
\end{cases}
 +
</tex>
 +
* Cоставим массив из всех <tex>n</tex> элементов множества <tex>A</tex>, упорядочим его по первой координате, построим на нём дерево отрезков с сохранением подмассива в каждой вершине<br>[[Файл:tree_built.png]]
  
==Построение дерева и запрос операции==
+
* Все подмассивы в вершинах получившегося дерева отрезков упорядочим по следующей координате<br>[[Файл:sorted_y.png]]
Алгоритм построения такого "усеченного" дерева отрезков будет выглядеть следующим образом:<br>
 
* Cоставить массив из всех <tex>n</tex> элементов множества <tex>A</tex>, упорядочить его по первой координате
 
* Построить на нём дерево отрезков с сохранением подмассива в каждой вершине
 
* Все подмассивы в вершинах получившегося дерева отрезков упорядочить по следующей координате, после чего повторить построение дерева для каждого из них
 
  
Псевдокод:
+
* Повторим построение дерева для каждого из них (координата последняя, поэтому в вершинах этих деревьев мы уже ничего строить не будем — подмассивы в каждой вершине можно не сохранять)<br>[[Файл:tree_completed.png]]
   build_normal_tree(element[] array)
+
<br>
  {
+
===Псевдокод===
       //построение одномерного дерева отрезков на массиве array с сохранением подмассива в каждой вершине
+
   '''buildSubarrayTree'''('''element[]''' array):
   }
+
       <font color=green>// построение одномерного дерева отрезков на массиве array с сохранением подмассива в каждой вершине </font>
 +
    
 +
  '''buildNormalTree'''('''element[]''' array):
 +
      <font color=green> // построение обычного одномерного дерева отрезков на массиве array </font>
 
    
 
    
   get_inside_array(vertex)
+
   '''getInsideArray'''(vertex v):
  {
+
       <font color=green>// получение подмассива, сохраненного в вершине vertex </font>
       //получение подмассива, сохраненного в вершине vertex
 
  }
 
 
    
 
    
   build_compressed_tree(element[] array, int coordinate = 0)  
+
   '''buildCompressedTree'''('''element[]''' array, '''int''' coordinate = 1):  <font color=green>// рекурсивная процедура построения сжатого дерева отрезков</font>
  {
+
      '''if''' coordinate < p  
      //собственно, построение сжатого дерева отрезков
+
            sort(array, coordinate)                               <font color=green>// сортировка массива по нужной координате </font>
      if (coordinate < p)
+
            segmentTree = buildSubarrayTree(array);
      {
+
            '''foreach''' v: vertex '''in''' segmentTree
        sort(array, coordinate); //сортировка массива по нужной координате
+
                buildCompressedTree(getInsideArray(v), coordinate + 1);
        segment_tree = build_normal_tree(array);
+
      '''if''' coordinate == p
        for (each vertex in segment_tree)
+
            sort(array, coordinate)
        {
+
            buildNormalTree(array);
            build_compressed_tree(inside_array(each), coordinate + 1);
+
 
        }
+
==Анализ полученной структуры==
      }
+
Легко понять, что сжатое <tex>p</tex>-мерное дерево отрезков будет занимать <tex>O(n\log^{p-1}\,n)</tex> памяти: превращение обычного дерева в дерево с сохранением всего подотрезка в каждой вершине будет увеличивать его размер в <tex>O(\log\,n)</tex> раз, а сделать это нужно будет <tex>p-1</tex> раз. Но расплатой станет невозможность делать произвольный запрос модификации: в самом деле, если появится новый элемент, то это приведёт к тому, что мы должны будем в каком-либо дереве отрезков по второй или более координате добавить новый элемент в середину, что эффективно сделать невозможно. Что касается запроса веса, он будет полностью аналогичен запросу в обычном <tex>p</tex>-мерном дереве отрезков за <tex>O(\log^p\,n)</tex>.
  }
+
 
 +
==См. также==
 +
* [[Дерево отрезков. Построение]]
 +
* [[Многомерное дерево отрезков]]
 +
==Источники информации==
 +
* [http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]
 +
* [http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2  Википедия — Дерево отрезков]
  
При такой оптимизации асимптотика размера структуры составит <tex>O(n\,log^{p-1}\,n)</tex>, а запрос будет аналогичен запросу в обычном <tex>p</tex>-мерном дереве отрезков за <tex>O(log^p\,n)</tex>. Но расплатой станет невозможность делать произвольный запрос модификации: в самом деле, если появится новый элемент, то это приведёт к тому, что мы должны будем в каком-либо дереве отрезков по второй или более координате добавить новый элемент в середину, что эффективно сделать невозможно.
+
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Дерево отрезков]]

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

Задача:
Пусть имеется множество [math]A[/math], состоящее из [math]n[/math] взвешенных точек в [math]p[/math]-мерном пространстве. Необходимо быстро отвечать на запрос о суммарном весе точек, находящихся в [math]p[/math]-мерном прямоугольнике [math](x_a,x_b),(y_a,y_b),\dots,(z_a,z_b)[/math]

Вообще говоря, с поставленной задачей справится и обычное [math]p[/math]-мерное дерево отрезков. Для этого достаточно на [math]i[/math]-том уровне вложенности строить дерево отрезков по всевозможным [math]i[/math]-тым координатам точек множества [math]A[/math], а при запросе использовать на каждом уровне бинарный поиск для установления желаемого подотрезка. Очевидно, запрос будет делаться за [math]O(\log^p\,n)[/math] времени, а сама структура данных будет занимать [math]O(n^p)[/math] памяти.

Оптимизация

Для уменьшения количества занимаемой памяти можно провести оптимизацию [math]p[/math]-мерного дерева отрезков. Для начала, будем использовать дерево отрезков с сохранением всего подотрезка в каждой вершине. Другими словами, в каждой вершине дерева отрезков мы будем хранить не только какую-то сжатую информацию об этом подотрезке, но и все элементы множества [math]A[/math], лежащие в этом подотрезке. На первый взгляд, это только увеличит объем структуры, но не все так просто. При построении будем действовать следующим образом — каждый раз дерево отрезков внутри вершины будем строить не по всем элементам множества [math]A[/math], а только по сохраненному в этой вершине подотрезку. Действительно, незачем строить дерево по всем элементам, когда элементы вне подотрезка уже были «исключены» и заведомо лежат вне желаемого [math]p[/math]-мерного прямоугольника. Такое «усеченное» многомерное дерево отрезков называется сжатым (англ. compressed).

Построение дерева

Рассмотрим алгоритм построения сжатого дерева отрезков на примере множества [math]A[/math], состоящего из [math]4[/math]-х взвешенных точек в [math]2[/math]-мерном пространстве (плоскости):

[math] p=2,~~n=4,~~A: \begin{cases} (1, 3), \mbox{weight}=7 \\ (2, 1), \mbox{weight}=1 \\ (3, 3), \mbox{weight}=8 \\ (4, 2), \mbox{weight}=5 \end{cases} [/math]

  • Cоставим массив из всех [math]n[/math] элементов множества [math]A[/math], упорядочим его по первой координате, построим на нём дерево отрезков с сохранением подмассива в каждой вершине
    Tree built.png
  • Все подмассивы в вершинах получившегося дерева отрезков упорядочим по следующей координате
    Sorted y.png
  • Повторим построение дерева для каждого из них (координата последняя, поэтому в вершинах этих деревьев мы уже ничего строить не будем — подмассивы в каждой вершине можно не сохранять)
    Tree completed.png


Псевдокод

  buildSubarrayTree(element[] array):
     // построение одномерного дерева отрезков на массиве array с сохранением подмассива в каждой вершине 
  
  buildNormalTree(element[] array):
      // построение обычного одномерного дерева отрезков на массиве array 
  
  getInsideArray(vertex v):
     // получение подмассива, сохраненного в вершине vertex 
  
  buildCompressedTree(element[] array, int coordinate = 1):   // рекурсивная процедура построения сжатого дерева отрезков
      if coordinate < p 
           sort(array, coordinate)                                // сортировка массива по нужной координате 
           segmentTree = buildSubarrayTree(array);
           foreach v: vertex in segmentTree 
                buildCompressedTree(getInsideArray(v), coordinate + 1);
      if coordinate == p
            sort(array, coordinate)
            buildNormalTree(array);

Анализ полученной структуры

Легко понять, что сжатое [math]p[/math]-мерное дерево отрезков будет занимать [math]O(n\log^{p-1}\,n)[/math] памяти: превращение обычного дерева в дерево с сохранением всего подотрезка в каждой вершине будет увеличивать его размер в [math]O(\log\,n)[/math] раз, а сделать это нужно будет [math]p-1[/math] раз. Но расплатой станет невозможность делать произвольный запрос модификации: в самом деле, если появится новый элемент, то это приведёт к тому, что мы должны будем в каком-либо дереве отрезков по второй или более координате добавить новый элемент в середину, что эффективно сделать невозможно. Что касается запроса веса, он будет полностью аналогичен запросу в обычном [math]p[/math]-мерном дереве отрезков за [math]O(\log^p\,n)[/math].

См. также

Источники информации