Сжатое многомерное дерево отрезков

Задача:

Пусть имеется множество [math]A[/math], состоящее из [math]n[/math] взвешенных точек в [math]p[/math]-мерном пространстве. Необходимо быстро отвечать на запрос о суммарном весе точек, находящихся в [math]p[/math]-мерном прямоугольнике [math](x_a,x_b),(y_a,y_b),\,...\,,(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]-мерного прямоугольника. Такое "усеченное" многомерное дерево отрезков называется сжатым.

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

Рассмотрим алгоритм построения сжатого дерева отрезков на следующем примере:

[math] p=2, 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], упорядочим его по первой координате, построим на нём дерево отрезков с сохранением подмассива в каждой вершине
  

• Все подмассивы в вершинах получившегося дерева отрезков упорядочим по следующей координате
  

• Повторим построение дерева для каждого из них (координата последняя, поэтому в вершинах этих деревьев мы уже ничего строить не будем — подмассивы в каждой вершине можно не сохранять)
  

Псевдокод

  build_subarray_tree(element[] array):
     //построение одномерного дерева отрезков на массиве array с сохранением подмассива в каждой вершине 
  
  build_normal_tree(element[] array):
      //построение обычного одномерного дерева отрезков на массиве array 
  
  get_inside_array(vertex v):
     //получение подмассива, сохраненного в вершине vertex 
  
  build_compressed_tree(element[] array, int coordinate = 1):   //рекурсивная процедура построения сжатого дерева отрезков
      if coordinate < p 
           sort(array, coordinate);                                //сортировка массива по нужной координате 
           segment_tree = build_subarray_tree(array);
           for each (vertex v in segment_tree) 
                build_compressed_tree(inside_array(v), coordinate + 1);
      if coordinate == p
            sort(array, coordinate);
            build_normal_tree(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].

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

• MAXimal :: algo :: Дерево отрезков
• Википедия — Дерево отрезков