Структуры данных

Segment Tree: Запросы на отрезках

Цели урока

  • Понять задачу Range Query + Update
  • Построить Segment Tree
  • Реализовать query и update за O(log n)
  • Узнать расширения: min, max, lazy propagation

Предварительные знания

  • Деревья
  • Деревья

Есть биржевые котировки за год - 365 чисел. Пользователь спрашивает: 'какая максимальная цена с 15 марта по 20 июня?'. И таких запросов тысячи, плюс цены обновляются. Segment Tree делает это за микросекунды.

  • Биржевые данные - min/max за период
  • Текстовые редакторы - подсчёт символов в range
  • Игры - damage на области карты
  • Мониторинг - агрегация метрик за временные окна

Range-деревья Бентли и классика спортивного программирования

Segment tree вырос из работ по вычислительной геометрии конца 1970-х. Джон Бентли предложил эту идею около 1977 года, изучая задачи об агрегатах на интервалах, а в 1980 году Бентли и Дерик Вуд опубликовали разбор range searching, где формализовали, как сбалансированное дерево над отрезками отвечает на интервальные запросы за логарифмическое время. Многие годы структура жила в основном в литературе по геометрии и базам данных. Вторую жизнь она получила в спортивном программировании, где стала базовым инструментом: задачи, смешивающие сумму на отрезке, минимум на отрезке и точечные обновления, встречаются настолько часто, что segment tree вместе с lazy propagation для range update сегодня считается обязательным знанием для соревнований вроде ICPC и Codeforces.

Задача Range Query

**Задача:** массив из n чисел. Много запросов двух типов:

  1. **query(l, r):** сумма элементов на отрезке [l, r]
  2. **update(i, val):** изменить arr[i] = val
Структураqueryupdate
МассивO(n)O(1)
Prefix SumO(1)O(n)
**Segment Tree****O(log n)****O(log n)**

Segment Tree - компромисс: оба типа операций за O(log n)!

Когда Segment Tree лучше Prefix Sum?

Структура Segment Tree

Segment Tree - бинарное дерево, где каждый узел отвечает за отрезок массива.

  • **Корень** хранит операцию на всём массиве
  • **Листья** - отдельные элементы
  • **Внутренние узлы** - результат операции над детьми
  • Высота = O(log n)

Что хранит корень Segment Tree для суммы?

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

**Сложность построения:** O(n) - каждый элемент обрабатывается константное число раз.

Сколько памяти нужно для Segment Tree из n элементов?

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

**Три случая:** не пересекается → 0, полностью внутри → вернуть, частично → рекурсия.

Сложность query(l, r) в Segment Tree:

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

**Сложность:** O(log n) - обновляем только путь от листа до корня.

Segment Tree поддерживает не только сумму: min, max, GCD, XOR - любую ассоциативную операцию!

При update(i, val) сколько узлов дерева меняются?

Segment Tree

  • Узел хранит результат операции на отрезке
  • Build: O(n), Query: O(log n), Update: O(log n)
  • Работает для sum, min, max, gcd, xor...
  • Lazy propagation для range update

Связанные структуры

Segment Tree - универсальный инструмент, но есть альтернативы для специфичных задач.

  • Fenwick Tree (BIT) — Проще для суммы, меньше памяти
  • Sparse Table — O(1) запрос для идемпотентных операций

Связанные уроки

  • ds-09-trees-intro — Структура дерева лежит в основе рекурсивного разбиения диапазона
  • ds-21-fenwick-tree — Дерево Фенвика решает суммы на диапазоне компактнее
  • ds-28-sparse-table — Sparse Table даёт O(1) запросы на статических диапазонах
  • alg-19-divide-conquer — Дерево рекурсивно делит диапазоны - идея разделяй и властвуй
  • db-09-indexes-btree — Индексы баз данных тоже ускоряют запросы по диапазонам данных
  • alg-36-prefix-sum
Segment Tree: Запросы на отрезках

0

1

Войти