Изменения

Перейти к: навигация, поиск

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

324 байта добавлено, 11:24, 7 июня 2011
Нет описания правки
==Структура==
[[Файл:compressed_tree.png|thumb|400px|right|Сжатое двумерное дерево отрезков, построенное по четырем точкам (x,y) на плоскости. Красным отмечены координаты, по которым производилась сортировка.]]
Вообще говоря, с поставленной задачей справится и обычное <tex>p</tex>-мерное дерево отрезков. Если дерево строить по всем элементам массива, то запрос операции на <tex>p</tex>-мерном прямоугольнике c помощью такой структуры будет выполняться за <tex>O(\frac{1}{S}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>-мерного прямоугольника. Для этого будем использовать сохранение всего подмассива в каждой вершине дерева отрезков.
77
правок

Навигация