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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Структура)
м (rollbackEdits.php mass rollback)
 
(не показано 69 промежуточных версий 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> памяти.
  
==Структура==
+
==Оптимизация==
[[Файл:compressed_tree.png|thumb|400px|right|Сжатое двумерное дерево отрезков, построенное по четырем точкам (x,y) на плоскости. Красным отмечены координаты, по которым производилась сортировка.]]
+
Для уменьшения количества занимаемой памяти можно провести оптимизацию <tex>p</tex>-мерного дерева отрезков. Для начала, будем использовать дерево отрезков с сохранением всего подотрезка в каждой вершине. Другими словами, в каждой вершине дерева отрезков мы будем хранить не только какую-то сжатую информацию об этом подотрезке, но и все элементы множества <tex>A</tex>, лежащие в этом подотрезке. На первый взгляд, это только увеличит объем структуры, но не все так просто. При построении будем действовать следующим образом каждый раз дерево отрезков внутри вершины будем строить не по всем элементам множества <tex>A</tex>, а только по сохраненному в этой вершине подотрезку. Действительно, незачем строить дерево по всем элементам, когда элементы вне подотрезка уже были «исключены»  и заведомо лежат вне желаемого <tex>p</tex>-мерного прямоугольника. Такое «усеченное»  многомерное дерево отрезков называется '''сжатым''' (англ. ''compressed'').
Вообще говоря, с поставленной задачей справится и обычное <tex>p</tex>-мерное дерево отрезков. Если дерево строить по всем элементам массива, то запрос операции на <tex>p</tex>-мерном прямоугольнике c помощью такой структуры будет выполняться за <tex>O(\frac{1}{p}log^p\,S)</tex>, а сама структура будет занимать порядка <tex>O(S)</tex> памяти, где <tex>S</tex> количество элементов в <tex>p</tex>-мерном массиве. Если дерево строить по элементам множества <tex>A</tex>, то асимптотики изменятся на <tex>O(log^p\,n)</tex> и <tex>O(n^p)</tex> соответственно. Однако, можно провести следующую оптимизацию — каждый раз дерево отрезков внутри вершины будем строить только по тем элементам, которые встречаются в отрезке, за который отвечает эта вершина. Действительно, другие элементы уже были "исключены" и заведомо лежат вне желаемого <tex>p</tex>-мерного прямоугольника. Для этого будем использовать сохранение всего подмассива в каждой вершине дерева отрезков.
 
  
==Построение дерева и запрос операции==
+
==Построение дерева==
Алгоритм построения такого "усеченного" дерева отрезков будет выглядеть следующим образом:<br>
+
Рассмотрим алгоритм построения сжатого дерева отрезков на примере множества <tex>A</tex>, состоящего из <tex>4</tex>-х взвешенных точек в <tex>2</tex>-мерном пространстве (плоскости):<br>
* Cоставить массив из всех <tex>n</tex> элементов множества <tex>A</tex>, упорядочить его по первой координате
+
 
* Построить на нём дерево отрезков с сохранением подмассива в каждой вершине
+
<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>[[Файл:tree_completed.png]]
 
<br>
 
<br>
Псевдокод:
+
===Псевдокод===
   build_normal_tree(element[] array)
+
   '''buildSubarrayTree'''('''element[]''' array):
  {
+
       <font color=green>// построение одномерного дерева отрезков на массиве array с сохранением подмассива в каждой вершине </font>
       //построение одномерного дерева отрезков на массиве array с сохранением подмассива в каждой вершине
+
    
   }
+
  '''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>. Но расплатой станет невозможность делать произвольный запрос модификации: в самом деле, если появится новый элемент, то это приведёт к тому, что мы должны будем в каком-либо дереве отрезков по второй или более координате добавить новый элемент в середину, что эффективно сделать невозможно.
+
[[Категория: Дискретная математика и алгоритмы]]
==Источники==
+
[[Категория: Дерево отрезков]]
[http://e-maxx.ru/algo/export_segment_tree Дерево отрезков на e-maxx.ru]
 

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

См. также

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