Информатика / Алгоритмы и анализ данных

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

Дерево отрезков делит массив на интервалы и хранит сумму каждого узла. Точечное изменение и сумма произвольного диапазона выполняются за O(log n), память занимает O(n).

Опубликовано: Обновлено:

Формула

$$T[v]=T[2v]+T[2v+1],\quad Q(L,R)=\sum_{i=L}^{R}a_i$$
Схема Канонические части запроса [2; 5]
Запрос [2; 5]427136[2][3][4; 5]2 + 7 + (1 + 3) = 13

При разбиении из примера запрос состоит из узлов [2], [3] и [4; 5]. Их суммы 2, 7 и 4 дают 13.

Обозначения

$a_i$
элемент массива, число
$T[v]$
сумма сегмента в узле v, число
$[L,R]$
границы сегмента узла, индекс
$Q(l,r)$
запрос суммы на диапазоне, число
$mid$
граница деления сегмента, индекс

Условия применения

Массив должен иметь фиксированный индексированный диапазон, а операция объединения сумм — быть ассоциативной. Для суммы нейтральный элемент равен нулю. Удобна рекурсивная модель узла [L,R] с разбиением mid=floor((L+R)/2); пустой запрос возвращает 0.

Ограничения

Дерево отрезков сложнее и обычно расходует больше памяти, чем дерево Фенвика. Присваивание на всём диапазоне без lazy propagation дорого, а реализация должна соблюдать границы сегментов. При статическом массиве и запросах без обновлений быстрее бывает один префиксный массив.

Подробное объяснение

Дерево отрезков представляет массив двоичным разбиением. Корень отвечает за весь [1,n], его дети — за левую и правую половины, а лист содержит один элемент. Во внутреннем узле хранится сумма детей, поэтому значение родителя можно пересчитать после изменения одного листа.

Запрос [l,r] сравнивается с текущим [L,R]. Если сегмент целиком внутри запроса, его сумма добавляется сразу. Если пересечения нет, возвращается ноль. Иначе алгоритм спускается к детям и складывает два результата; каждый уровень оставляет лишь ограниченное число пограничных сегментов.

При точечном изменении лист получает новое значение, затем обратный путь к корню пересчитывает суммы. Высота сбалансированного дерева равна O(log n), а запрос и обновление посещают O(log n) узлов в обычном анализе. Неполное последнее разбиение не нарушает корректность.

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

Сумма — только один пример моноидного агрегата: похожим образом хранят минимум, максимум или gcd, если определены нейтральный элемент и операция. Для изменения целого диапазона применяют lazy propagation, откладывая одинаковую прибавку в вершине до момента, когда понадобится спуск.

Как пользоваться формулой

  1. Постройте листы по значениям массива, затем снизу вверх сложите суммы левого и правого ребёнка в каждом внутреннем узле.
  2. Для запроса передайте узлу его [L,R] и искомый [l,r]; полностью покрытый узел верните, непересекающийся отбросьте.
  3. При частичном пересечении вычислите mid и сложите результаты рекурсивного спуска в левое и правое поддеревья.
  4. Для изменения a[i] замените лист и поднимитесь к корню, пересчитывая T[v]=T[2v]+T[2v+1].
  5. Проверьте результат наивным сложением диапазона и отдельно протестируйте одиночный лист и весь массив.

Историческая справка

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

Общая математическая основа — ассоциативность операции. Она объясняет, почему один и тот же способ разбиения используется для суммы, минимума или наибольшего общего делителя, хотя нейтральные значения и допустимые обновления в этих задачах различаются. Порядок объединения также сохраняют для некоммутативных операций.

В современных исследованиях рассматриваются многомерные деревья и диапазонные обновления. Они расширяют базовую модель, но не означают, что простая структура автоматически обрабатывает любую операцию над диапазоном. Здесь разобран только одномерный вариант с точечным присваиванием и суммой; персональный приоритет этому учебному описанию не назначается.

Историческая линия формулы

У дерева отрезков нет одного общепринятого автора в смысле персональной формулы. Это семейство двоичных разбиений интервала, оформленное в учебниках по структурам данных и алгоритмам; атрибуцию корректнее связывать с развитием алгоритмической техники, а не с одним именем.

Пример

Пусть a = [4; 2; 7; 1; 3; 6]. Корень [1; 6] хранит 23 и делится на [1; 3] с суммой 13 и [4; 6] с суммой 10. В левом поддереве разбиение даёт [1; 2] и [3], в правом — [4; 5] и [6]. Найдём сумму [2; 5]. Из левой половины берём лист [2] со значением 2 и лист [3] со значением 7. Справа полностью покрыт узел [4; 5] с суммой 1 + 3 = 4. Ответ равен 2 + 7 + 4 = 13. Непокрытые листья 1 и 6 в сумму не входят. Присвоим a₃ = 5. Лист меняется на −2, узел [1; 3] становится 11, корень — 21. Новый запрос [2; 5] даёт 2 + 5 + 4 = 11. Прямая проверка всего массива: 4 + 2 + 5 + 1 + 3 + 6 = 21; сумма уменьшилась с 23 ровно на 2.

Частая ошибка

Не забывайте, что границы обычно включительные: переход к [L,mid] и [mid+1,R] не должен оставлять дырку. Ошибка в условии полного покрытия приводит к двойному учёту. При присваивании нельзя просто прибавить новое значение — нужна разность или запись листа с пересчётом. Наконец, индексы массива и номера узлов дерева — разные пространства; смешивание их ломает адресацию.

Практика

Задачи с решением

Запрос после построения

Условие. Массив [2,5,1,4,3]. Найдите сумму на [2,4].

Решение. При разбиении [1; 5] на [1; 3] и [4; 5] запрос [2; 4] собирает листья [2], [3] и [4]. Сумма равна 5 + 1 + 4 = 10.

Ответ. 10

Точечное изменение

Условие. В массиве [2,5,1,4,3] присвойте a[4]=9. Найдите сумму [3,5].

Решение. После обновления элементы [1,9,3], сумма диапазона равна 13.

Ответ. 13

Дополнительные источники

  • https://cp-algorithms.com/data_structures/segment_tree.html
  • https://arxiv.org/abs/1811.01226

Связанные формулы

Информатика

Двоичный поиск: максимальное число сравнений ключа

$C_{\max}(n)=\lfloor\log_2 n\rfloor+1,\quad n\ge1$

Двоичный поиск в отсортированном массиве отбрасывает половину диапазона после каждого трехстороннего сравнения. В худшем случае для n≥1 требуется не более ⌊log₂ n⌋+1 итераций.

Информатика

Поиск в ширину: кратчайший путь по числу рёбер

$d(s)=0,\qquad d(v)=d(u)+1\quad\text{при первом открытии }v\text{ из }u$

Поиск в ширину, или BFS, находит минимальное число переходов от стартовой вершины в невзвешенном графе. Очередь обрабатывает вершины слоями, поэтому первое открытие уже задаёт кратчайшее расстояние.

Информатика

Поиск в глубину: дерево обхода и времена входа и выхода

$u\text{ — предок }v\iff t_{in}(u)<t_{in}(v)<t_{out}(v)<t_{out}(u),\quad u\ne v$

Поиск в глубину, или DFS, полностью исследует одну ветвь графа перед возвратом к следующей. Времена входа и выхода образуют вложенные интервалы и позволяют проверять родство в дереве обхода.