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

Дерево Фенвика для динамических префиксных сумм

Дерево Фенвика хранит частичные суммы массива так, чтобы точечное изменение и сумма на префиксе выполнялись за O(log n). Сумму от l до r получают вычитанием двух префиксов.

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

Формула

$$B_i=\sum_{j=i-\operatorname{lowbit}(i)+1}^{i}a_j,\quad \operatorname{lowbit}(i)=i\mathbin{\&}(-i),\quad Q(l,r)=S(r)-S(l-1)$$
Схема Как дерево собирает S(7)
S(7) = B₇ + B₆ + B₄1234567B₄: 1–4B₆: 5–6B₇7 − 1 = 6; 6 − 2 = 4; 4 − 4 = 0

Запрос 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] получается как разность двух префиксов. Это использует обратимость сложения: для минимума аналогичная разность не имеет смысла. Если нужно присвоить новое значение, сначала находят Δ = новое − старое; передача нового значения в операцию добавления без этого шага изменит массив неверно.

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

  1. Переведите индекс во внутреннюю нумерацию с единицы и задайте tree[1..n] нулями или постройте его из массива.
  2. Для добавления delta к a[i] прибавляйте delta к tree[i], затем переходите к i = i + lowbit(i), пока i не превысит n.
  3. Для префикса S(r) складывайте tree[r], затем переходите к r = r − lowbit(r), пока r не станет нулём.
  4. Для отрезка [l,r] вычислите S(r) и S(l−1), затем вычтите левый префикс из правого.
  5. Сверьте результат прямым проходом на малом массиве и проверьте границы индексов.

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

Питер М. Фенвик описал структуру в статье «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

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

Информатика

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

$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, полностью исследует одну ветвь графа перед возвратом к следующей. Времена входа и выхода образуют вложенные интервалы и позволяют проверять родство в дереве обхода.