Изменения

Пусть имеется множество <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>

Вообще говоря, с поставленной задачей справится и [[Многомерное дерево отрезков|обычное <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>

p=2, ~~n=4,~~A:

'''build_subarray_treebuildSubarrayTree'''('''element[]''' array): <font color=green>//построение одномерного дерева отрезков на массиве array с сохранением подмассива в каждой вершине </font>

'''build_normal_treebuildNormalTree'''('''element[]''' array): <font color=green> //построение обычного одномерного дерева отрезков на массиве array </font>

'''get_inside_arraygetInsideArray'''(vertex v): <font color=green>//получение подмассива, сохраненного в вершине vertex </font>

'''build_compressed_treebuildCompressedTree'''('''element[]''' array, '''int''' coordinate = 1): <font color=green>//рекурсивная процедура построения сжатого дерева отрезков</font>

sort(array, coordinate); <font color=green>//сортировка массива по нужной координате </font> segment_tree segmentTree = build_subarray_treebuildSubarrayTree(array); '''forforeach''' each (v: vertex v '''in''' segment_tree) segmentTree build_compressed_treebuildCompressedTree(inside_arraygetInsideArray(v), coordinate + 1);

sort(array, coordinate); build_normal_treebuildNormalTree(array);