Конспект: дерево отрезков и дерево Фенвика

Понятия

Дерево отрезков - листья = элементы, внутренний узел = СВЁРТКА своего отрезка (любая ассоциативная операция: сумма, min, max, gcd). Запрос [l, r] собирается из O(log n) узлов, целиком лежащих внутри диапазона (три случая на узле: вне / целиком внутри / частично); обновление элемента чинит O(log n) узлов на пути к корню. И запрос, и обновление - O(log n).

Префиксные суммы - плоская альтернатива: запрос O(1), но обновление O(n) (ломает все префиксы). Годятся только для СТАТИЧЕСКОГО массива.

Дерево Фенвика (BIT) - компактно для СУММ: один массив, ячейка i хранит блок длиной lowbit(i) = i & (−i). Префикс - складывать, СБРАСЫВАЯ младший бит (i −= lowbit); обновление - ПРИБАВЛЯЯ (j += lowbit); оба O(log n). Сумма [l,r] = префикс(r) − префикс(l−1). Только ОБРАТИМЫЕ операции (сумма, xor) - min/max не умеет. Индексация с 1.

Отложенные обновления (lazy) - дают дереву отрезков обновление ДИАПАЗОНА за O(log n): целиком накрытые узлы помечают меткой и правят свёртку оптом, не спускаясь к детям; метку проталкивают детям (push_down) по требованию. И запрос, и обновление делают push_down при спуске.

Неявный ключ - позиция элемента в последовательности, вычисленная по размерам левых поддеревьев; в узле она не хранится. split(t, k) - первые k элементов и остальные; merge(a, b) - склейка, где всё из a левее всего из b.

Сумма в неявном дереве: total = x + total(l) + total(r), у пустого узла 0. Два split выделяют [l, r), его корень хранит ответ; два merge возвращают части. Разворот сохраняет total, но меняет суммы по прежним позициям.

Алгоритм Мо - офлайн-ответ на запросы к отрезкам: сортировка по блоку ⌊l/√n⌋ и по r внутри блока, два указателя с пересчётом ответа за O(1) на шаг; O((n + q)·√n) шагов.

Что унести

Задача главы - диапазонный запрос И обновление за ЛОГАРИФМ, а не за n. Решение зависит от того, меняются ли данные и какая операция.

структура	запрос	обновление	операции	заметка
префиксные суммы	O(1)	O(n)	обратимые	только статика
дерево Фенвика	O(log n)	O(log n)	суммы/xor	компактно, просто
дерево отрезков	O(log n)	O(log n)	любая ассоциативная	универсально
+ lazy	O(log n)	диапазон O(log n)	+ обновление отрезка	ленивые метки

Выбор: чисто чтения статического массива → префиксные суммы; динамические СУММЫ → Фенвик (проще, компактнее); min/max/gcd или сложные операции → дерево отрезков; обновление ДИАПАЗОНА → дерево отрезков с lazy.

Две сквозные идеи: (1) ИЕРАРХИЯ свёрток уравнивает запрос и обновление в O(log n), потому что элемент входит лишь в log n вложенных отрезков (развитие приёма дополнения); (2) ЛЕНИВОСТЬ - откладывать распространение изменений до востребования (как кеши, copy-on-write, растущий массив, splay).

Декартово дерево по неявному ключу - массив с правкой в середине за O(log n) в ожидании: вставка, удаление, перестановка кусков - по два-три split и merge; разворот отрезка - флаг в корне куска, проталкиваемый лениво. На ста тысячах элементов - 97 узлов на операцию против 41 тысячи сдвигов у списка.

Если ответ не складывается из половинок (число различных значений), дерево отрезков не годится; если запросы известны заранее, их переставляют по Мо: на 20 тысячах запросов - 2.4 миллиона шагов указателей против 230 миллионов.

Ловушки джокера

Префиксные суммы при обновлениях - каждое обновление O(n). Для динамики - дерево/Фенвик.

В запросе дерева отрезков спускаться в целиком-внутренние узлы - их свёртка готова, углубление теряет O(log n).

Забыть починить свёртки вверх после обновления листа - запросы соврут.

Фенвик для min/max - не работает (нет вычитания). Только обратимые операции.

Фенвик с индекса 0 - lowbit(0)=0 зацикливает. Индексация с 1.

Забыть push_down в ЗАПРОСЕ при lazy - прочитаешь устаревшие свёртки детей.

Перезаписать метку lazy вместо КОМБИНИРОВАНИЯ - потеряешь прежнее отложенное изменение.

Забыл пересчитать size или протолкнуть флаг. Ошибки не будет - split молча режет не там, и последовательность тихо становится другой.

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

Проверь себя

Почему запрос дерева отрезков - O(log n), а не O(n)?

Чем дерево отрезков лучше префиксных сумм и когда лучше префиксы?

Что хранит ячейка Фенвика и как собирается префиксная сумма?

Чем Фенвик ограничен по сравнению с деревом отрезков?

Как отложенные метки дают обновление диапазона за O(log n) и почему это не портит данные?

Как без хранения позиций найти k-й элемент декартова дерева и разрезать его по позиции?

В каком порядке алгоритм Мо обходит запросы и откуда берётся оценка (n + q)·√n?