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

## Определение
**Дерево отрезков (англ. Segment tree)** - очень мощная и гибкая структура данных, позволяющая быстро отвечать на самые разные запросы на отрезках.
P.S. Обычно дерево отрезков реализует на полуинтервалах $[l:r)$ , поэтому это скорее дерево полуинтервалов, но вы можете писать так, как вам больше нравится.
## Описание структуры
Структура представляет собой дерево, листьями которого являются элементы исходного массива. Другие вершины этого дерева имеют по $2$ ребенка и содержат значение функции от своих детей. Таким образом, корень содержит результат искомой функции от всего массива $[0…n−1]$. левый ребёнок корня содержит результат функции на $[0…\frac{n}{2}]$, а правый, соответственно результат на $[\frac{n}{2}+1…n−1]$. И так далее, продвигаясь вглубь дерева.
## Свойства
Высота такого дерева есть величина $Θ(log(n))$
На каждом новом уровне длина отрезка уменьшается вдвое. Этот факт будет ключевым для оценки асимптотики.
Дерево также содержит менее $2n$ вершин: первый уровень дерева отрезков содержит одну вершину (корень), второй уровень — в худшем случае две вершины, на третьем уровне в худшем случае будет четыре вершины, и так далее, пока число вершин не достигнет $n$. Таким образом, число вершин в худшем случае оценивается суммой $n + \frac{n}{2} + \frac{n}{4} + ... + 1 < 2n$
## Построение
Процесс построения дерева отрезков по заданному массиву $a$ можно делать эффективно следующим образом, снизу вверх: сначала запишем значения элементов $a[i]$ в соответствующие листья дерева, затем на основе них посчитаем значения для вершин предыдущего уровня как сумму значений в двух листьях, затем аналогичным образом посчитаем значения для ещё одного уровня, и т.д. Удобно описывать эту операцию рекурсивно: мы запускаем процедуру построения от корня дерева отрезков, а сама процедура построения, если её вызвали не от листа, вызывает себя от каждого из двух сыновей и суммирует вычисленные значения, а если её вызвали от листа — то просто записывает в себя значение этого элемента массива.

Асимптотика построения дерева отрезков составит, таким образом, $O(n)$

## Запрос минимума
Рассмотрим теперь задачу, где у нас есть какой-то массив $a$ и множество запросов $q$, где каждый запрос описывается двуми индексами $[l,r)$. Нам требуется за время $O(log (n))$ находить минимум на отрезке.

Построим дерево отрезков для нашего массива $a$, где в каждой вершине мы будем хранить минимум для принадлежащему ей отрезка.
Опишем, как с помощью такой структуры решить данную задачу.
Мы знаем, что во всех вершинах лежат минимумы для различных отрезков длины степени двух.
Сделаем тоже рекурсивную функцию, рассмотрев три случая:
* Если отрезок вершины лежит целиком в отрезке запроса, то вернуть записанное в нем значение.
* Если отрезки вершины и запроса не пересекаются, то вернуть MAX_VALUE
* Иначе разделиться рекурсивно на 2 половины и вернуть меньшее из двух значений этой функции от обоих детей.

## Запрос обновления
Добавим к исходной задаче запросы второго вида, что мы хотим изменить значение по какому-то индексу в массиве.

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