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

---

Дерево отрезков — структура данных, позволяющая находить значение некоторой ассоциативной функции ${\displaystyle f}$ на произвольном отрезке ${\displaystyle a[i],a[i+1],\dots ,a[j]}$ массива за асимптотику ${\displaystyle O(\log n)}$. Наиболее часто в качестве ${\displaystyle f}$ берутся функции суммы, произведения, максимум и минимум.

Дерево отрезков представляет собой корневое дерево, листьями которого являются элементы исходного массива, а другие вершины имеют по 2 ребенка. Каждой вершине в соответствие поставлен интервал, являющийся объединением интервалов ее детей (если у вершины есть дети), либо интервал, содержащий конкретный элемент массива (для листьев). Кроме того, для каждой вершины хранится значение некоторой ассоциативной функции ${\displaystyle f}$ на данном интервале. Данное дерево будет иметь логарифмическую высоту, так как количество уровней не будет превышать ${\displaystyle \log _{2}n}$

Пусть наш массив ${\displaystyle a}$ имеет ${\displaystyle n}$ элементов: ${\displaystyle a[0],a[1],\dots ,a[n-1]}$.

Выберем ${\displaystyle h}$ такое, что ${\displaystyle 2^{h}\geq n}$. Дополним наш массив справа нейтральными элементами так, чтобы его длина равнялась ${\displaystyle 2^{h}}$. Тогда для хранения дерева отрезков, построенного на элементах массива ${\displaystyle a}$, нам понадобится массив ${\displaystyle b}$ из ${\displaystyle 2^{h+1}}$ ячеек.

---