Информатика / Алгоритмы и анализ данных
Дерево Фенвика для динамических префиксных сумм
Дерево Фенвика хранит частичные суммы массива так, чтобы точечное изменение и сумма на префиксе выполнялись за O(log n). Сумму от l до r получают вычитанием двух префиксов.
Формула
Запрос 7 → 6 → 4 → 0 объединяет три непересекающихся блока: [7], [5; 6] и [1; 4].
Обозначения
- $a_j$
- Элемент исходного массива, единицы данных
- $B_i$
- Хранимая сумма блока с правым концом i, единицы данных
- $n$
- Количество элементов, —
- $i,j,l,r$
- Индексы от 1 до n; l ≤ r, —
- $\operatorname{lowbit}(i)$
- Значение младшего установленного двоичного бита i, —
- $S(r)$
- Сумма элементов от 1 до r, S(0) = 0, единицы данных
- $Q(l,r)$
- Сумма на включённом отрезке [l,r], единицы данных
Условия применения
Используется нумерация от 1 до n и точечное прибавление к элементу; префикс нулевой длины имеет сумму 0. Хранимые значения допускают сложение и вычитание, а тип данных вмещает все промежуточные суммы. lowbit(i) вычисляют только для положительного индекса в принятой целочисленной модели.
Ограничения
Базовая структура поддерживает прибавление и сумму. Присваивание требует вычислить разность с прежним значением; произвольные интервальные обновления нуждаются в расширении. Минимум нельзя получить вычитанием двух префиксных минимумов. Суммы могут переполнять машинный тип даже при небольших элементах.
Подробное объяснение
В ячейке Bᵢ лежит не сумма всех элементов до i, а сумма блока длиной lowbit(i), заканчивающегося в i. Например, индекс 12 в двоичной записи равен 1100, его младший установленный бит имеет значение 4, поэтому B₁₂ охватывает элементы 9–12. Эти блоки позволяют собрать любой префикс без пересечений.
Для префикса r сначала берём Bᵣ и уменьшаем индекс на lowbit(r). Последний установленный бит исчезает, а следующий блок покрывает ещё не учтённую часть слева. При r = 7 последовательность индексов равна 7 → 6 → 4 → 0; блоки [7], [5; 6] и [1; 4] вместе дают весь префикс [1; 7].
При прибавлении Δ к aᵢ обновляются все хранимые блоки, содержащие этот элемент. Переход i ← i + lowbit(i) ведёт к следующему такому блоку. Для n = 8 изменение a₃ затронет B₃, B₄ и B₈. Остальные блоки не содержат третий элемент, поэтому их суммы сохраняются.
И запрос, и обновление проходят логарифмическое число блоков. Память остаётся O(n), поскольку на индекс хранится одна сумма. Построение простым последовательным добавлением стоит O(n log n), хотя существует и линейное построение; оценку отдельной операции нельзя путать со стоимостью инициализации.
Отрезок [l; r] получается как разность двух префиксов. Это использует обратимость сложения: для минимума аналогичная разность не имеет смысла. Если нужно присвоить новое значение, сначала находят Δ = новое − старое; передача нового значения в операцию добавления без этого шага изменит массив неверно.
Как пользоваться формулой
- Переведите индекс во внутреннюю нумерацию с единицы и задайте tree[1..n] нулями или постройте его из массива.
- Для добавления delta к a[i] прибавляйте delta к tree[i], затем переходите к i = i + lowbit(i), пока i не превысит n.
- Для префикса S(r) складывайте tree[r], затем переходите к r = r − lowbit(r), пока r не станет нулём.
- Для отрезка [l,r] вычислите S(r) и S(l−1), затем вычтите левый префикс из правого.
- Сверьте результат прямым проходом на малом массиве и проверьте границы индексов.
Историческая справка
Питер М. Фенвик описал структуру в статье «A New Data Structure for Cumulative Frequency Tables», опубликованной в Software—Practice and Experience в 1994 году. Исходная задача была связана с динамическими накопленными частотами, необходимыми при арифметическом кодировании: требовались и быстрые суммы, и изменение отдельных частот.
В современном изложении структура известна как Binary Indexed Tree или дерево Фенвика. Её компактность определяется двоичным разбиением индекса: каждый элемент массива хранит сумму блока с длиной, равной младшему установленному биту. Важна именно организация частичных сумм, а не отдельная новая операция сложения.
Позднейшие учебные применения включают динамические суммы и подсчёт инверсий после сжатия координат. При таком переносе исходные частоты могут заменяться другими аддитивными данными, но ограничения операции сохраняются. Простая версия не превращается автоматически в структуру для любого диапазонного агрегата.
Историческая линия формулы
Авторство структуры связывают со статьёй Питера М. Фенвика 1994 года о накопленных частотах. Это атрибуция организации блоков и обновлений; сами префиксные суммы и аддитивные запросы относятся к более широкой традиции обработки массивов.
Пример
Пусть a = [3; 1; 4; 1; 5; 9]. Найдём сумму на отрезке от 2 до 5 и затем увеличим третий элемент на 2. Первые значения дерева: B₁ = 3, B₂ = 4, B₃ = 4, B₄ = 9, B₅ = 5, B₆ = 14. Запрос S(5) берёт B₅ + B₄ = 5 + 9 = 14, а S(1) = B₁ = 3. Поэтому Q(2,5) = 14 − 3 = 11. При обновлении a₃ на +2 меняются B₃ с 4 до 6 и B₄ с 9 до 11; следующий индекс 8 уже за пределами n = 6. После обновления S(5) = 5 + 11 = 16, S(1) осталось 3, новый ответ 13. Прямая проверка по изменённому массиву даёт 1 + 6 + 1 + 5 = 13. Единицы суммы совпадают с единицами элементов; индексы и lowbit безразмерны.
Частая ошибка
Нельзя запускать добавление с i = 0: lowbit(0) = 0, и цикл не продвинется. В запросе индекс уменьшают, в обновлении увеличивают. Не передавайте новое значение вместо приращения Δ. Для суммы [l; r] вычитают S(l − 1), а не S(l). Объём машинного типа выбирают по возможной сумме всех элементов, учитывая отрицательные приращения.
Практика
Задачи с решением
Префикс
Условие. Массив [2,7,1,8,2]. Увеличьте третий элемент на 4 и найдите S(4).
Решение. Новый массив [2,7,5,8,2], S(4)=22.
Ответ. 22
Отрезок
Условие. Массив [5,0,3,4,1,6]. Найдите Q(2,5), затем уменьшите a[4] на 3.
Решение. Сначала 0+3+4+1=8; после изменения 0+3+1+1=5.
Ответ. 8; затем 5
Дополнительные источники
- https://doi.org/10.1002/spe.4380240306
- https://blogs.asarkar.com/assets/docs/algorithms/Fenwick%20Tree%20-%20Fenwick.pdf
- https://visualgo.net/en/fenwicktree
Связанные формулы
Информатика
Двоичный поиск: максимальное число сравнений ключа
Двоичный поиск в отсортированном массиве отбрасывает половину диапазона после каждого трехстороннего сравнения. В худшем случае для n≥1 требуется не более ⌊log₂ n⌋+1 итераций.
Информатика
Поиск в ширину: кратчайший путь по числу рёбер
Поиск в ширину, или BFS, находит минимальное число переходов от стартовой вершины в невзвешенном графе. Очередь обрабатывает вершины слоями, поэтому первое открытие уже задаёт кратчайшее расстояние.
Информатика
Поиск в глубину: дерево обхода и времена входа и выхода
Поиск в глубину, или DFS, полностью исследует одну ветвь графа перед возвратом к следующей. Времена входа и выхода образуют вложенные интервалы и позволяют проверять родство в дереве обхода.