Дерево Фенвика: суммы на младшем бите

Если ты понимаешь, что ячейка Фенвика хранит блок длиной в младший бит индекса, что префикс собирается сбрасыванием младшего бита, а обновление - прибавлением, и чем Фенвик уже дерева отрезков, листай до «Теперь сам».

Как думаешь, нужен ли для сумм целый лес узлов

Дерево отрезков решает задачу, но хранит ~2n узлов со ссылками - и памяти много, и константа чувствительна. А задача про СУММЫ (и вообще ОБРАТИМЫЕ операции, где есть «вычитание») имеет приятное свойство: сумму на [l, r] можно получить как префикс(r) − префикс(l−1). Значит хватит уметь быстро считать ПРЕФИКСНЫЕ суммы с обновлениями - а это проще, чем произвольный диапазон. Возникает мысль: нельзя ли обойтись ОДНИМ массивом, без дерева-со-ссылками, спрятав иерархию прямо в индексы? Оказывается, да - если разбить префикс на блоки, чьи длины - степени двойки, подсказанные ДВОИЧНОЙ записью индекса. Так рождается дерево Фенвика: вся структура - в битах.

На что это похоже

Сдача монетами по степеням двойки. Чтобы отсчитать сумму до 13, ты не считаешь 13 единиц, а берёшь заранее заготовленные «пачки»: пачку на 8, пачку на 4, монету на 1 (13 = 8 + 4 + 1 - это её двоичная запись 1101). Три пачки вместо тринадцати штук. Дерево Фенвика хранит именно такие «пачки-суммы»: ячейка отвечает за блок-степень-двойки, и любой префикс набирается из O(log n) пачек - ровно по числу единичных битов, как размен суммы монетами номиналами 1, 2, 4, 8, ….

Механизм: младший бит правит всем

Заведём массив bit[1..n] (индексация с 1; в примерах ниже n = 13). Ячейка bit[i] хранит сумму блока элементов длиной lowbit(i), где lowbit(i) = i & (−i) - значение младшего единичного бита i:

lowbit(i) = i & (-i)      # напр. lowbit(12)=4 (1100 -> 100), lowbit(6)=2, lowbit(8)=8
bit[i] покрывает элементы (i − lowbit(i), i]   -- блок длины lowbit(i), кончающийся на i

Префиксная сумма до i (a[1] + … + a[i]) - идём вниз, СБРАСЫВАЯ младший бит:

префикс(i):
    s = 0
    пока i > 0:
        s += bit[i]
        i -= lowbit(i)      # сбросить младший бит - перейти к предыдущему блоку
    вернуть s

Обновить элемент a[j] += delta - идём вверх, ПРИБАВЛЯЯ младший бит:

обновить(j, delta):
    пока j <= n:
        bit[j] += delta
        j += lowbit(j)      # прибавить младший бит - к следующей ячейке, покрывающей j

В обоих циклах индекс за шаг теряет или получает один бит, поэтому шагов - число битов, O(log n). Сумма на [l, r] = префикс(r) − префикс(l−1).

Правило

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

Разбор: почему сбрасывание младшего бита даёт правильный префикс

Разберём, почему O(log n) блоков действительно покрывают префикс [1..i] без пропусков и нахлёстов. Ячейка bit[i] покрывает блок (i − lowbit(i), i] - он кончается на i и имеет длину младшего бита. Взяв bit[i], мы покрыли верхушку префикса; осталось покрыть [1 .. i − lowbit(i)] - а это префикс до нового индекса i' = i − lowbit(i), полученного СБРАСЫВАНИЕМ младшего бита. Повторяем: берём bit[i'], сбрасываем его младший бит, и так пока индекс не станет 0. Каждый шаг убирает ровно один единичный бит из двоичной записи, значит шагов - число единичных битов, не больше log n. Блоки стыкуются встык (каждый начинается там, где кончился предыдущий по индексу) и не перекрываются - в сумме дают весь [1..i]. Это тот же «размен по степеням двойки»: двоичная запись i говорит, какие блоки-пачки сложить. Красота в том, что вся иерархия закодирована битами индекса, и никакого дерева хранить не нужно.

Разбор: почему Фенвик уже дерева отрезков, но его всё равно любят

Честное сравнение двух структур для одной задачи. Дерево отрезков УНИВЕРСАЛЬНЕЕ: оно работает с любой АССОЦИАТИВНОЙ операцией (сумма, min, max, gcd, произведение матриц), потому что просто объединяет свёртки детей. Дерево Фенвика опирается на ВЫЧИТАНИЕ (сумма[l,r] = префикс(r) − префикс(l−1)), поэтому годится для ОБРАТИМЫХ операций - сумм, xor, - но НЕ для min/max (у минимума нет «обратной операции», из префикс(r) и префикс(l−1) минимум на отрезке не восстановить). Зачем же Фенвик, если он менее универсален? За компактность и простоту: один массив вместо ~2n узлов со ссылками (меньше памяти), крошечный код (несколько строк на lowbit), отличная локальность (последовательный массив - дружелюбен к кешу), меньшая константа. Поэтому для САМОЙ частой задачи - «динамические префиксные суммы / количества» - берут Фенвика: он быстрее и проще. А когда нужна не сумма, а min/max/gcd на отрезке или сложные обновления диапазона - дерево отрезков. Это ещё один пример «универсальный инструмент против специализированного»: Фенвик - острая заточка под суммы.

Что ломается без этого

Первая ошибка - применять Фенвика к min/max: из префиксных минимумов минимум на отрезке не получить (нет вычитания) - для min/max нужно дерево отрезков. Фенвик - для обратимых операций (суммы, xor, счётчики). Вторая - перепутать направление циклов: в ЗАПРОСЕ индекс УМЕНЬШАЕТСЯ (−= lowbit), в ОБНОВЛЕНИИ УВЕЛИЧИВАЕТСЯ (+= lowbit); поменяешь местами - получишь мусор. Третья - индексация с нуля: Фенвик классически работает с индексов 1 (иначе lowbit(0) = 0 даёт бесконечный цикл); массив держат [1..n], а элементы сдвигают. Четвёртая - думать, что Фенвик хранит сами элементы: bit[i] - это СУММА БЛОКА, а не a[i]; чтобы узнать один элемент, считают префикс(i) − префикс(i−1).

Зачем это в работе

Дерево Фенвика - самая частая структура для динамических префиксных сумм и подсчётов: сколько элементов меньше данного среди уже добавленных (подсчёт инверсий, ранги в реальном времени), скользящие суммы и счётчики, частотные таблицы с обновлениями, двумерные версии для сумм по прямоугольникам. Его обожают в олимпиадном программировании и используют в аналитике за компактность и скорость. Понимать его важно как (1) практичный инструмент «суммы + обновления за log n в пять строк», (2) яркий пример того, как ИЕРАРХИЮ можно спрятать в двоичном представлении индекса, без явных узлов - изящный трюк, показывающий связь между структурой данных и битовым представлением чисел. И как урок выбора: для сумм - Фенвик (проще, компактнее), для произвольной ассоциативной свёртки - дерево отрезков (универсальнее). Обе решают задачу этой главы - диапазонный запрос и обновление за логарифм, а не за n; следующий урок - как деревом отрезков обновлять сразу ЦЕЛЫЙ диапазон.

Теперь сам

Чтобы посчитать префиксную сумму до индекса 11 в дереве Фенвика, какие ячейки bit[…] сложить? (11 в двоичном - 1011.) Сколько их и почему это O(log n)?