Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Определение

Дерево отрезков — это древовидная структура данных, используемая для эффективного решения задач запроса на отрезке, позволяя со сложностью $O(\log_2 n)$ вычислять значение ассоциативной функции на нём.

Ассоциативная функция - такая функция $f(a, b)$, для которой выполняется условие $f(a, b) = f(b, a)$ для любых $a$ и $b$.

Также для ассоциативной функции должен существовать нейтральный элемент $n_0$ такой, что: $f(a, n_0) = a$ для любых значений $a$.

Примеры ассоциативных функций:

1. Сумма; $n_0 = 0$
2. Произведение; $n_0 = 1$
3. Минимум; $n_0 = +\infty$
4. Максимум; $n_0 = -\infty$
5. Битовые операции:
   1. И; $n_0 = 2^P - 1$, при этом $n_0$ должен быть больше максимального элемента в данных
   2. Или; $n_0 = 0$
   3. Исключающее или; $n_0 = 0$

---

Структура дерева отрезков

Структура является бинарным деревом, в листьях которого содержатся исходные данные. Другие вершины содержат значения вычисленной функции $f$ от значений детей.

Соответственно, в корне дерева будет находиться значение функции на всём заданном отрезке. В левом ребёнке корня - значение функции на левой половине отрезка: $[0; \frac{n}{2})$; в правом ребёнке корня - значение функции на правой половине отрезка: $[\frac{n}{2}; n)$. И т.д.

---

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

Будем строить дерево для массива данных $\{1, 2, 3, 4, 5, 6, 7\}$ и функции поиска суммы на отрезке $f(a, b) = a + b$.

Существуют два подхода к построению дерева: снизу и сверху.

Построение снизу

Уровень листьев необходимо заполнить элементами из массива данных, при этом дополнив количество листьев до степени 2 нейтральными элементами.

Т.к. количество входных данных равно $7$, то необходимо:

1. Создать $8 = 2^3$ листьев
2. Скопировать входные данные в листья по порядку
3. Оставшиеся листья заполнить нейтральным элементом $n_0 = 0$

Далее посчитать уровень узлов над листьями с помощью функции $f$. Для этого нужно вычислить значение функции $f$, используя элементы из соседних листьев. Получим последовательность $\{3, 7, 11, 7\}$

Необходимо повторять данную операцию, пока не будет построено дерево (будет найдено значение корневого узла).

Второй уровень дерева: $\{10, 18\}$.

Значение в корневом узле: $28$.

Дерево отрезков построено.

Построение сверху

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

Изначально есть только корневой узел:

Значение в нём будет получено после применения функции $f$ к значениям его детей.

Построим левое поддерево.

Четвёртый уровень дерева - уровень листьев, поэтому в этот узел назначаем первый элемент из входных данных.

Добавив правый лист, можно вычислить значение в узле на 3-ем уровне.

И так далее:

По аналогии можно построить правое поддерево корневого узла и вычислить значение в нём.

После построения дерево отрезков содержит $2 \bullet 2^P$ узлов, где $2^P$ - ближайшая к размеру входных данных степень 2.

Сложность данной операции при обоих подходах построения составляет $O(N)$ как по времени, так и по памяти.

Способ организации данных в дереве отрезков

Существует 2 подхода для организации данных в этой структуре:

1. Хранение бинарным деревом с узлами, содержащими ссылки на детей
2. Хранение дерева в массиве

Дерево отрезков в виде дерева

Плюсы:

1. Может содержать большее количество элементов в отличие от реализации на массиве

Минусы:

1. Не поддерживается кэширование в процессоре
2. Реализовывать тяжелее, чем на массиве

Дерево отрезков на массиве

Плюсы:

1. Простая реализация
2. Поддерживается кэширование в процессоре

Минусы:

1. Необходимо выделять память под массив, что можно быть неосуществима при большом размере входных данных

Как организовать дерево отрезков на массиве

Если какой-либо узел бинарного дерева находится в массиве по индексу $i$, то его левый потомок будет находиться в массиве по индексу $2 \bullet i$, правый - по индексу $2 \bullet i + 1$.

Корень дерева находится в ячейке массива по индексу $1$.

Обратиться к предку узла, находящегося в массиве на позиции $j$, можно по индексу $\lfloor \frac{j}{2} \rfloor$.

Тогда построенное выше дерево отрезков в массиве будет выглядеть так:

Индекс   Узел
0        Ничего
1        28 - корневой узел
2        |  10 - левый потомок корня
3        |  18 - правый потомок корня
4           |  3 - левый потомок узла [2]
5           |  7 - правый потомок узла [2]
6           |  11 - левый потомок узла [3]
7           |  7 - правый потомок узла [3]
8              |  1 - левый потомок узла [4]
9              |  2 - правый потомок узла [4]
10             |  3 - левый потомок узла [5]
11             |  4 - правый потомок узла [5]
12             |  5 - левый потомок узла [6]
13             |  6 - правый потомок узла [6]
14             |  7 - левый потомок узла [7]
15             |  0 - правый потомок узла [7]

Вычисление значения функции на отрезке (запрос в дерево отрезков)

Данная операция позволяет вычислить значение ассоциативной функции $f$ на полуинтервале $[l; r)$ в построенном дереве отрезков со сложностью $O(\log_2 N)$, где $0 \le l \lt r \lt N$.

Данную операцию также можно реализовывать сверху и снизу.

Запрос в дерево отрезков снизу

Выполним запрос для полуинтервала $[1; 5)$ для построенного выше дерева отрезков с ассоциативной функцией $f(a, b) = a + b$.

Исходя из данных запроса, необходимо найти сумму выделенных элементов дерева:

{.align-center}

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

Устанавливаем левую границу на элемент $l$, правую - на элемент $r - 1$.

Выполняем данные действия, пока левая граница не совпадёт с правой

1. Если элемент на левой границе является правым сыном, то необходимо "совместить" его с накопленным результатом с помощью функции $f$, а левую границу сдвинуть на 1 элемент вправо.
2. Если элемент на правой границе является левым сыном, то необходимо "совместить" его с накопленным результатом с помощью функции $f$, а правую границу сдвинуть на 1 элемент влево.
3. Установить левую границу на родительский элемент.
4. Установить правую границу на родительский элемент.

Установим значение результата для левой и правых частей на нейтральный элемент: $leftRes = n_0 = 0$ $rightRes = n_0 = 0$

Устанавливаем левую границу на элемент с индексом $2$, правую - на элемент с индексом $4$.

Так как элемент на левой границе является правым сыном, то необходимо совместить его значение с левым результатом $leftRes = f(0, 2) = 2$ и сдвинуть левую границу на 1 элемент вправо.

Элемент на правой границе является левым сыном, поэтому необходимо совместить значение в этом узле с правым результатом $rightRes = f(0, 5) = 5$ и сдвинуть правую границу на 1 элемент влево.

Теперь необходимо переместить левую и правую границы в родительские узлы текущих границ.

Узел левой и правой границы совпадает, поэтому можно остановить подъём.

Результат операции запроса к отрезку $[1; 5)$ будет равен: $f(leftRes,\ f([l],\ rightRes)) = 2 + (7 + 5) = 14$, где $[l]$ - значение в узле левой границы. $14$ - сумма элементов на полуинтервале $[1; 5)$.

Запрос в дерево отрезков сверху

Выполним аналогичный запрос к построенному выше дереву отрезков: необходимо найти значение функции $f(a, b) = a + b$ на полуинтервале $[1; 5)$.

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

Запускаем рекурсивно из корня дерева.

1. Устанавливаем левую границу на левого потомка текущего узла.
2. Устанавливаем правую границу на правого потомка текущего узла.
3. Если полуинтервал, образующийся левой и правой границами, не имеет пересечения с запрашиваемым отрезком, то необходимо вернуть нейтральный элемент $n_0$.
4. Если полуинтервал, образующийся левой и правой границами, полностью содержится внутри запрашиваемого отрезка, то необходимо вернуть элемент в текущем узле.
5. Иначе необходимо выполнить этот алгоритм для узлов на левой и правой границах и вернуть вычисленное функцией $f$ значение от полученных данных.

Запускаем данный алгоритм от корневого узла, который содержит значение функции на отрезке $[0; 7]$.

Отрезок $[0; 7]$ имеет пересечение с запрашиваемым отрезком и не содержится внутри него, поэтому необходимо вычислить значения от потомков корневого узла.

Для левого потомка:

Данный узел содержит значение функции на отрезке $[0; 3]$.

Отрезок $[0; 3]$ имеет пересечение с запрашиваемым отрезком и не содержится внутри него, поэтому необходимо вычислить значения от потомков текущего узла.

Для левого потомка:

Данный узел содержит значение функции на отрезке $[0; 1]$.

Отрезок $[0; 1]$ имеет пересечение с запрашиваемым отрезком и не содержится внутри него, поэтому необходимо вычислить значения от потомков текущего узла.

Его левый потомок отвечает за отрезок $[0; 0]$, который не имеет пересечений с запрашиваемым отрезком, следовательно, рекурсивный вызов для этого узла вернёт нейтральный элемент.

Правый потомок отвечает за отрезок $[1; 1]$, который полностью содержится внутри запрашиваемого отрезка, следовательно, рекурсивный вызов для этого узла вернёт значение в этом узле.

Соответственно для текущего узла будет возвращено значение $f(n_0, [1]) = f(0, 2) = 2$, где $[1]$ - значение на $1$ позиции в отрезке.

Для правого потомка:

Данный узел содержит значение функции на отрезке $[2, 3]$. Этот отрезок полностью содержится в запрашиваемом, поэтому рекурсивный вызов для этого узла вернёт значение значение в этом узле.

Соответственно, в левом потомке корневого узла, необходимо вычислить значение функции $f$ от его потомков: $f(2, 7) = 2 + 7 = 9$.

Для правого потомка корневого узла:

Данный узел содержит значение функции на отрезке $[4; 7]$.

Отрезок $[4; 7]$ имеет пересечение с запрашиваемым отрезком и не содержится в нём, поэтому необходимо вычислить значение от потомков текущего узла.

Для левого потомка:

Данный узел содержит значение функции на отрезке $[4; 5]$.

Отрезок $[4; 5]$ имеет пересечение с запрашиваемым отрезком и не содержится в нём, поэтому необходимо вычислить значение от потомков текущего узла.

Левый потомок текущего узла отвечает за значение функции на отрезке $[4; 4]$, который полностью включается в запрашиваемый отрезок. Следовательно, рекурсивный вызов для данного узла вернёт значение в этом узле.

Правый потомок текущего узла отвечает за значение функции на отрезке $[5; 5]$, который не имеет пересечений с запрашиваемым отрезком. Следовательно, рекурсивный вызов для данного узла вернёт нейтральный элемент.

Соответственно, для текущего узла будет возвращено значение $f([4], n_0) = f(5, 0) = 5 + 0 = 5$, где $[4]$ - элемент во входных данных на позиции $4$.

Для правого потомка:

Данный узел отвечает за значение функции на отрезке $[6; 7]$. Данный отрезок не имеет пересечений с запрашиваемым отрезком, следовательно, рекурсивный вызов для данного узла вернёт нейтральный элемент.

Для правого потомка корневого узла, необходимо вычислить значение функции $f$ от полученных значений: $f(5, 0) = 5 + 0 = 5$.

Для корневого узле, необходимо вычислить значение функции $f$ от полученных значений рекурсивных вызовов для его потомков: $f(9, 5) = 9 + 5 = 14$. $14$ - значение функции $f$ на запрашиваемом полуинтервале $[1; 5)$.

Обновление одного элемента в дереве отрезков

Данная операция позволяет заменить значение одного элемента из входных данных в уже построенном дереве со сложностью $O(\log_2 N)$.

Чтобы заменить значение в узле дерева отрезков, необходимо:

1. Изменить значение в данном узле
2. Пересчитать значения в узлах на пути от изменённого узле до корня дерева

Заменим значение в узле по индексу $4$ в построенном выше дереве с 5 на 10.

Для этого сначала обновим значение в изменённом узле.

Пересчитаем значения в узлах, находящихся на пути от изменённого узла до корня дерева, вычислив для каждого из них значение функции $f$ от их потомков.

Значение в узле на третьем уровне дерева обновится на $f([4], [5]) = f(10, 6) = 10 + 6 = 16$, где $[4]$ и $[5]$ - значения в массиве входных данных на позициях $4$ и $5$.

Значение в узле на втором уровне дерева обновится на $f(16, 7) = 16 + 7 = 23$.

Значение в корне дерева обновится на $f(10, 23) = 10 + 23 = 33$.

Значения всех узлов на пути от обновлённого узла до корня дерева обновлены.

Реализация дерева отрезков

Псевдокод

структура Дерево Отрезков:
    типы данных:
        Элемент
        Узел (содержит элемент,
              позволяет обратиться к предку и потомкам)
        Индекс

    атрибуты:
        func - ассоциативная функция, 
               по которой строится дерево
        n0 - нейтральный элемент
        N - количество хранимых элементов, степень 2
        tree - массив размера 2*N, заполненный n0

    методы:
        построить дерево(Массив элементов data):
            проверка, что длина data <= N
            для i в [0; N):
                tree[i + N] = data[i]
            перестроить дерево(i + N, 2 * N)

        перестроить дерево(Индекс l, Индекс r):
            пока l > 0:
                если l - правый ребёнок:
                    tree[родитель l] = func(tree[l - 1], tree[l])
                    увеличить l на 1
                если (r - 1) - левый ребёнок:
                    tree[родитель r] = func(tree[r - 1], tree[r])
                    уменьшить r на 1
                для i в [l, r) с шагом 2:
                    tree[родитель i] = func(tree[i], tree[i + 1])
                l = родитель l
                r = родитель r

        обновить элемент(Индекс p, Элемент value):
            если p не принадлежит полуинтервалу [0; N):
                завершить выполнение функции
            увеличить p на N
            tree[p] = value
            перестроить дерево(p, p + 1)

        запросить значение функции на отрезке(Индекс l, Индекс r):
            если l >= r или полуинтервал [l; r) не содержится внутри [0; N):
                вернуть n0
            увеличить l на N
            увеличить r на N - 1
            result = n0
            пока l < r:
                если l - правый ребёнок:
                    result = func(result, tree[l])
                    увеличить l на 1
                если r - левый ребёнок:
                    result = func(tree[r], result)
                    уменьшить r на 1
                l = родитель l
                r = родитель r
        если l совпадает с r:
            result = func(result, tree[l])
        вернуть result

C++

Подключение необходимых модулей:

#include <cmath>   // для вычисления ближайшей степени 2 к числу
#include <vector>  // динамический массив для хранения структуры

// аргументы шаблона:
// N - количество элементов для хранения
// ValueType - хранимый тип данных
// FunctionType - тип функции для вычисления её на отрезке
template <
    std::size_t N,
    typename ValueType,
    typename FunctionType>
class SegmentTree {
public:
    typedef ValueType value_type;
    typedef FunctionType function_type;
    typedef std::size_t size_type;

private:
    typedef std::vector<value_type> container_type;

public:
// конструкторы, деструктор и операторы присваивания
    SegmentTree(
        const value_type &neutral_value = value_type(),
        const function_type &function = function_type()
    ) : _tree(2 * size(), neutral_value), 
        _neutral(neutral_value), _func(function) {}

    // конструктор из последовательности
    template <typename InputIterator>
    SegmentTree(
        InputIterator first,
        InputIterator last,
        const value_type &neutral_value = value_type(),
        const function_type &function = function_type()
    ) : SegmentTree(neutral_value, function) {
        build(first, last);
    }

    SegmentTree(const SegmentTree &other) = default;

    SegmentTree(SegmentTree &&other) = default;

    ~SegmentTree() = default;

    SegmentTree &operator=(const SegmentTree &other) = default;

    SegmentTree &operator=(SegmentTree &&other) = default;

    // допустимое количество хранимых элементов
    // ближайшая степень 2, которая не меньше N
    static constexpr size_type size() {
        return std::pow(2, std::ceil(std::log2(N)));
    }

// основные функции
    // очистка дерева = заполнение его нейтральными элементами
    void clear() {
        std::fill(_tree.begin(), _tree.end(), _neutral);
    }

    // построить дерево заново из заданной последовательности
    // если длина последовательности превосходит size(),
    // то в дерево будет добавлено ровно size() элементов из 
    // последовательности
    template <typename InputIterator>
    void build(InputIterator first, InputIterator last) {
        clear();
        if (std::distance(first, last) > size())
            for (int i = 0; i < size(); ++i)
                _tree[i + size()] = *first++;
        else
            std::copy(first, last, _tree.begin() + size());
        _rebuild_tree(size(), 2 * size());
    }

    // назначение value по индексу index
    // должно выполняться: 0 <= index < size()
    void update(size_type index, const value_type &value) {
        if (index >= size())
            throw std::out_of_range("index out of range");
        index += size();
        _tree[index] = value;
        _rebuild_tree(index, index + 1);
    }

    // запросить значение функции на полуинтервале [l; r)
    // должно выполняться: 0 <= l < r <= size()
    value_type query(size_type l, size_type r) const {
        if (l >= r)
            throw std::invalid_argument("l >= r");
        if (l >= size() || r > size())
            throw std::out_of_range("index out of range");
        l += size();
        r += size() - 1;
        value_type result = _neutral;
        while (l < r) {
            if (_is_right_child(l)) {
                result = _func(result, _get_node_value(l));
                ++l;
            }
            if (_is_left_child(r)) {
                result = _func(result, _get_node_value(r));
                --r;
            }
            l = _parent(l);
            r = _parent(r);
        }
        if (l == r)
            result = _func(result, _get_node_value(l));
        return result;
    }

private:
// утилитарные методы

    // обновление дерева на отрезке
    // l, r - индексы в массиве, представляющем дерево
    // должно выполняться: 0 <= l < r <= 2 * size()
    void _rebuild_tree(size_type l, size_type r) {
        while (l > 0) {
            if (_is_right_child(l)) {
                _tree[_parent(l)] = _func(_get_node_value(l - 1), _get_node_value(l));
                ++l;
            }
            if (_is_left_child(r - 1)) {
                _tree[_parent(r)] = _func(_get_node_value(r - 1), _get_node_value(r));
                --r;
            }
            for (size_type i = l; i < r; i += 2)
                _tree[_parent(i)] = _func(_get_node_value(i), _get_node_value(i + 1));
            l = _parent(l);
            r = _parent(r);
        }
    }

// методы с узлами
    // переход к левому потомку
    static size_type _left_child(size_type node) {
        return 2 * node;
    }

    // переход к правому потомку
    static size_type _right_child(size_type node) {
        return 2 * node + 1;
    }

    // переход к родителю
    static size_type _parent(size_type node) {
        return node / 2;
    }

    // проверка, что node является левым сыном
    static bool _is_left_child(size_type node) {
        return !_is_root(node) && node % 2 == 0;
    }

    // проверка, что node является правым сыном
    static bool _is_right_child(size_type node) {
        return !_is_root(node) && node % 2 == 1;
    }

    // проверка, что node является корнем дерева
    static bool _is_root(size_type node) {
        return node < 2;
    }

    // получить значение в node
    // если node выходит на пределы дерева, 
    // будет возвращён нейтральный элемент
    value_type _get_node_value(size_type node) const {
        if (node >= 2 * size())
            return _neutral;
        return _tree[node];
    }

    // аналогично _get_node_value
    value_type operator[](size_type pos) const {
        return _get_node_values(pos);
    }

// операции итерации
    auto begin() const {
        return _tree.begin() + size();
    }

    auto end() const {
        return _tree.end();
    }

    auto cbegin() const {
        return _tree.cbegin() + size();
    }

    auto cend() const {
        return _tree.cend();
    }

private:
    container_type _tree;
    function_type _func;
    value_type _neutral;
};

Python

from typing import TypeVar, Callable, Iterable, overload

T = TypeVar('T')

class SegmentTree(Iterable[T]):
    def __init__(self,
                 n: int,
                 func: Callable[[T, T], T],
                 neutral: T):
        self._n = 2 ** (n - 1).bit_length()
        self._neutral = neutral
        self._func = func
        self._tree = [neutral for _ in range(2 * self._n)]

    def __len__(self) -> int:
        return self._n

    @overload
    def __getitem__(self, index: int) -> T:
        ...

    @overload
    def __getitem__(self, index: slice) -> Iterable[T]:
        ...

    @overload
    def __setitem__(self, index: int, value: T):
        ...

    @overload
    def __setitem__(self, index: slice, value: Iterable[T]):
        ...

    def __iter__(self) -> Iterable[T]:
        return iter(self[0:self._n])

    def clear(self):
        for i in range(len(self._tree)):
            self._tree[i] = self._neutral

    def build(self, data: Iterable[T]):
        self.clear()
        for i, item in zip(range(self._n), data):
            self._tree[i + self._n] = item
        self._rebuild_tree(self._n, 2 * self._n)

    def update(self, index: int, value: T):
        if index >= self._n:
            raise IndexError(f"Index {index} out of range [0, {self._n})")
        index += self._n
        self._tree[index] = value
        self._rebuild_tree(index, index + 1)

    def query(self, l: int, r: int) -> T:
        if l >= r:
            raise ValueError(f"Invalid range [{l}, {r})")
        if not (0 <= l < r <= self._n):
            raise IndexError(f"Range [{l}, {r}) out of range [0, {self._n})")
        l += self._n
        r += self._n - 1
        result = self._neutral
        while l < r:
            if self._is_right_child(l):
                result = self._func(result, self._get_node_value(l))
                l += 1
            if self._is_left_child(r):
                result = self._func(self._get_node_value(r), result)
                r -= 1
            l = self._parent(l)
            r = self._parent(r)
        if l == r:
            result = self._func(result, self._get_node_value(l))
        return result

    def _rebuild_tree(self, l, r):
        while l > 0:
            if self._is_right_child(l):
                self._tree[self._parent(l)] = self._func(
                    self._get_node_value(l - 1), self._get_node_value(l))
                l += 1
            if self._is_left_child(r - 1):
                self._tree[self._parent(r)] = self._func(
                    self._get_node_value(r - 1), self._get_node_value(r)
                )
                r -= 1
            for i in range(l, r, 2):
                self._tree[self._parent(i)] = self._func(
                    self._get_node_value(i), self._get_node_value(i + 1))
            l = self._parent(l)
            r = self._parent(r)

    def _left_child(self, node):
        return 2 * node

    def _right_child(self, node):
        return 2 * node + 1

    def _parent(self, node):
        return node // 2

    def _is_left_child(self, node):
        return not self._is_root(node) and node % 2 == 0

    def _is_right_child(self, node):
        return not self._is_root(node) and node % 2 == 1

    def _is_root(self, node):
        return node < 2

    def _get_node_value(self, node):
        if not (0 <= node < 2 * self._n):
            return self._neutral
        return self._tree[node]

    def __getitem__(self, index):
        if isinstance(index, slice):
            return self.__getitem__slice(index)
        return self.__getitem__single(index)

    def __getitem__slice(self, index: slice) -> Iterable[T]:
        start = index.start or 0
        stop = index.stop or self._n
        step = index.step or 1
        if not (0 <= start < stop <= self._n):
            raise IndexError(
                f"Range [{start}, {stop}) out of range [0, {self._n})")
        return (self._tree[i + self._n] for i in range(start, stop, step))

    def __getitem__single(self, index: int) -> T:
        if index >= self._n:
            raise IndexError(f"Index {index} out of range [0, {self._n})")
        return self._tree[index + self._n]

    def __setitem__(self, index, value):
        if isinstance(index, slice) and isinstance(value, Iterable):
            return self.__setitem__slice(index, value)
        if isinstance(index, int):
            return self.__setitem__single(index, value)
        raise TypeError("Invalid argument types")

    def __setitem__slice(self, index: slice, value: Iterable[T]):
        start = index.start or 0
        stop = index.stop or self._n
        step = index.step or 1
        if not (0 <= start < stop <= self._n):
            raise IndexError(
                f"Range [{start}, {stop}) out of range [0, {self._n})")
        for i, item in zip(range(start, stop, step), value):
            self._tree[i + self._n] = item
        self._rebuild_tree(start + self._n, stop + self._n)

    def __setitem__single(self, index: int, value: T):
        self.update(index, value)