Дерево запроса диапазона

В информатике дерево запросов диапазона , или RQT, — это термин, обозначающий структуру данных, которая используется для выполнения запросов диапазона и обновлений базового массива, который рассматривается как листья дерева. RQT, в принципе, представляют собой полные двоичные деревья со статической структурой, где каждый узел хранит результат применения фиксированной двоичной операции к диапазону листьев дерева (или элементам базового массива).

Дерево запросов диапазона использует O ( n хранилище ), где n — размер массива, на вершине которого строится структура, и может быть построено за время O ( n ). Деревья запросов диапазона поддерживают выполнение запросов диапазона и обновлений на его листьях за время O (log n ).

Деревья запросов диапазона обычно ошибочно называют деревьями сегментов или деревьями диапазонов ; оба эти термина являются неточными, поскольку они также относятся к другим уже существующим структурам.

Деревья запросов диапазона могут быть обобщены на пространства более высоких измерений , а также могут быть реализованы с помощью двух деревьев Фенвика, когда операции с диапазонами представляют собой суммы.

Описание структуры

Дерево запросов диапазона — это полное двоичное дерево , имеющее статическую структуру, что означает, что можно изменить его содержимое, но не его размер. Значения базового массива, над которым необходимо выполнить ассоциативную операцию, хранятся в листьях дерева, и количество значений должно быть дополнено до следующей степени двойки значением идентификатора для используемой ассоциативной операции.

Каждый узел дерева представляет интервал базового массива значений. Корневой узел представляет всю дополненную длину массива, а каждый из двух его дочерних узлов представляет первую и вторую половину интервала соответственно. Узлы в дереве генерируются рекурсивно таким образом, пока они не будут представлять один единственный элемент в базовом массиве.

Требования к хранению

Дерево запросов диапазона с базовым массивом размера n (дополненным до степени двойки) имеет n листьев, всего 2. ^log₂log2n +1 O( n узел, для которого требуется хранилище ).