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

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

История

Концепция дерева отрезков была впервые предложена в 1977 году американским учёным Джоном Бентли (Jon Louis Bentley) в работе «Solutions to Klee's rectangle problems». Бентли разработал эту структуру для решения задач вычислительной геометрии, в частности для эффективного нахождения пересечений прямоугольников. Впоследствии дерево отрезков стало широко применяться в олимпиадном программировании и алгоритмических задачах, благодаря своей универсальности и простоте реализации.

Основные принципы работы

Структура

Дерево отрезков строится на основе исходного массива A длины n. Каждый узел дерева хранит информацию о некотором отрезке [l, r) (левый индекс включительно, правый — исключительно). Корень дерева соответствует всему массиву [0, n). Листья дерева представляют отдельные элементы массива (отрезки длины 1). Внутренние узлы разбивают отрезок на две равные (или почти равные) части: левый дочерний узел отвечает за [l, mid), правый — за [mid, r), где mid = (l + r) // 2.

Хранение данных

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

Операции

Построение

Построение дерева отрезков выполняется за O(n). Алгоритм рекурсивно обходит дерево, начиная с корня. Для листьев (отрезков длины 1) значение узла равно значению соответствующего элемента массива. Для внутренних узлов значение вычисляется на основе значений дочерних узлов (например, сумма, минимум, максимум).

Запрос на отрезке

Запрос на отрезке [l, r) выполняется за O(log n). Алгоритм рекурсивно спускается по дереву. Если отрезок текущего узла полностью лежит внутри запрашиваемого отрезка, возвращается значение узла. Если отрезки не пересекаются, возвращается нейтральный элемент (например, 0 для суммы, +∞ для минимума, -∞ для максимума). Если отрезки пересекаются частично, рекурсивно обрабатываются левый и правый дочерние узлы, после чего их результаты комбинируются.

Обновление элемента

Обновление значения одного элемента массива (по индексу) выполняется за O(log n). Алгоритм находит лист, соответствующий изменяемому элементу, обновляет его значение, а затем поднимается вверх по дереву, пересчитывая значения всех узлов на пути от листа к корню.

Варианты и модификации

Дерево отрезков с массовыми обновлениями

Для поддержки обновления целого отрезка (например, прибавление числа ко всем элементам на отрезке) используется техника ленивых обновлений (lazy propagation). В этом случае каждый узел хранит не только значение, но и «отложенное» обновление, которое применяется к дочерним узлам только при необходимости (при запросе или дальнейшем обновлении). Это позволяет выполнять массовые обновления за O(log n).

Двумерное дерево отрезков

Для работы с двумерными массивами (матрицами) существует двумерное дерево отрезков. Оно строится как дерево отрезков по одной координате, в каждом узле которого хранится дерево отрезков по другой координате. Сложность запросов и обновлений составляет O(log² n). Применяется в задачах вычислительной геометрии и обработки изображений.

Дерево Фенвика

Дерево Фенвика (двоичное индексированное дерево) является более простой альтернативой дереву отрезков для задач, где требуется только сумма на отрезке и точечное обновление. Оно использует меньше памяти (n элементов) и быстрее работает на практике, но менее универсально.

Персистентное дерево отрезков

Персистентная версия дерева отрезков позволяет сохранять все предыдущие состояния структуры после обновлений. Каждое обновление создаёт новую версию, при этом изменённые узлы копируются, а неизменённые разделяются между версиями. Это позволяет выполнять запросы к историческим данным. Сложность по времени и памяти — O(log n) на операцию.

Применение

Олимпиадное программирование

Дерево отрезков является одной из ключевых структур данных в спортивном программировании. Оно используется для решения широкого круга задач: нахождение суммы, минимума, максимума на отрезке; поиск k-го нуля или единицы; вычисление количества инверсий; работа с интервалами и диапазонами.

Обработка запросов в реальном времени

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

Вычислительная геометрия

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

Базы данных

В некоторых системах управления базами данных (СУБД) используются аналоги деревьев отрезков для индексации интервальных данных (например, временных интервалов) и выполнения запросов на пересечение.

Пример реализации

Ниже приведён пример реализации дерева отрезков на языке Python для нахождения суммы на отрезке с точечными обновлениями:

```python class SegmentTree: def __init__(self, data): self.n = len(data) self.tree = [0] (4 self.n) self._build(data, 1, 0, self.n)

def _build(self, data, v, l, r): if r - l == 1: self.tree[v] = data[l] else: mid = (l + r) // 2 self._build(data, v2, l, mid) self._build(data, v2+1, mid, r) self.tree[v] = self.tree[v2] + self.tree[v2+1]

def update(self, pos, value): self._update(1, 0, self.n, pos, value)

def _update(self, v, l, r, pos, value): if r - l == 1: self.tree[v] = value else: mid = (l + r) // 2 if pos < mid: self._update(v2, l, mid, pos, value) else: self._update(v2+1, mid, r, pos, value) self.tree[v] = self.tree[v2] + self.tree[v2+1]

def query(self, l, r): return self._query(1, 0, self.n, l, r)

def _query(self, v, tl, tr, l, r): if l >= r: return 0 if l == tl and r == tr: return self.tree[v] mid = (tl + tr) // 2 return self._query(v2, tl, mid, l, min(r, mid)) + \ self._query(v2+1, mid, tr, max(l, mid), r) ```

Сравнение с другими структурами

Критика и ограничения

Дерево отрезков требует значительного объёма памяти (обычно 4n), что может быть проблемой для очень больших массивов (n > 10⁷). Для задач, где требуется только сумма на отрезке, более эффективным может быть дерево Фенвика. Реализация с ленивыми обновлениями усложняет код и замедляет работу в некоторых сценариях. Кроме того, дерево отрезков не поддерживает вставку и удаление элементов (для этого требуются сбалансированные деревья поиска, такие как декартово дерево).

Интересные факты

• В некоторых задачах олимпиадного программирования дерево отрезков используется для решения задач, которые на первый взгляд не связаны с интервалами, например, для поиска наименьшего общего предка (LCA) в дереве.
• Существует нерекурсивная реализация дерева отрезков (на основе массива с нумерацией узлов, начиная с n), которая работает быстрее за счёт отсутствия рекурсивных вызовов.
• Дерево отрезков может быть обобщено на произвольные ассоциативные операции (например, умножение матриц, нахождение наибольшего общего делителя).

Источники

• Bentley, J. L. (1977). «Solutions to Klee's rectangle problems». Carnegie-Mellon University.
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. (2013). «Алгоритмы: построение и анализ». 3-е издание. — М.: Вильямс.
• Окулов, С. М. (2004). «Программирование в алгоритмах». — М.: Бином. Лаборатория знаний.
• Статья «Segment tree» на сайте CP-Algorithms.