Первая страница / Визуализаторы / Деревья / Дерево отрезков /

Описание алгоритма

SegmentTree-Algorithm

Дерево отрезков

Дерево отрезков — это структура данных, для которой определены следующие операции:
  1) построение дерева из массива за O(N);
  2) нахождение суммы элементов с i-го по j-й за O(logN);
  3) изменение i-го элемента за O(logN).
Здесь N — это количество элементов массива, из которого построено дерево.
Структура занимает O(N) памяти. Вместо суммы можно находить произведение, минимум или максимум.

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

Дополним исходный массив нулевыми элементами так, чтобы их количество равнялось некоторой степени двойки. Теперь создадим набор элементов следующим образом: i-й элемент нашего набора будет суммой элемента c номером 2i и элемента с номером 2i+1 исходного набора. Построим еще один набор по тому же принципу. Продолжим процесс, пока не останется один элемент. Он будет корнем нашего дерева. Его сыновьями будут те элементы, суммой которых он является. Получим двоичное дерево, которое можно хранить в массиве. При этом, если корень — это элемент с номером 0, родителем элемента с номером index будет элемент с номером (index+1)/2-1. Левым сыном — элемент с номером (index+1)*2-1, правым — элемент с номером (index+1)*2.

Получение суммы

Будем использовать следующий алгоритм. Установим границы суммирования на соответствующие листья. Теперь, если элемент, попавший на левую границу, является правым сыном своего родителя, то добавим его к сумме. Аналогично для элемента, попавшего на правую границу. Поднимем границы, используя следующий код:
left = parent(left + 1);
right = parent(right - 1).
Закончим алгоритм, когда границы пересекутся. Если они попадут на один и тот же элемент, то добавим его к сумме.

Изменение элемента

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