Информатика · объяснение и практика
Дерево Фенвика: обновления и префиксные суммы по битам индекса
Дерево Фенвика для суммы:lowbit,префикс из нескольких блоков и обновление одного элемента без перестройки всех префиксов.

В теме Структуры данных · Учебная карта
В маршруте Графы, разрезы и динамические запросы · 10 тем
Главная мысль
Дерево Фенвика хранит специально выбранные суммы блоков и поддерживает добавление к одному элементу вместе с запросом префиксной суммы за логарифмическое число шагов. Здесь индексы начинаются с единицы;lowbit(i)=i&(-i)задаёт длину блока, заканчивающегося в i.
Каждая ячейка отвечает за свой блок
При нумерации с единицы ячейка T[i]хранит сумму от i−lowbit(i)+1 до i включительно. Например, для i=6 двоичная запись 110 имеет младшую единицу веса 2,поэтому блок покрывает элементы 5 и 6. Для i=4 младшая единица веса 4,поэтому блок идёт от 1 до 4.
Чтобы получить сумму первых i элементов, добавляют T[i]и переходят к i−lowbit(i). Каждый шаг снимает уже учтённый правый блок и продолжает слева. При достижении нуля все части префикса учтены. Ноль здесь служит границей окончания, а не обычной ячейкой, которую можно обновлять тем же правилом.
Собираем префикс на собственном массиве
Пусть массив с индексами 1…8 равен[2,5,1,4,3,6,0,7]. Для префикса до 6 нужны блок T[6],содержащий позиции 5 и 6 с суммой 9,и блок T[4],содержащий позиции 1…4 с суммой 12. Получаем 21,после чего следующий индекс становится 0.
Если увеличить элемент 3 на 2,меняются ячейки 3,4 и 8. Они содержат этот элемент в своих блоках. Ячейка 6 не меняется: её блок 5…6 не включает третью позицию. Новый префикс до 6 равен 9+14=23. Так обновляется только цепочка затронутых блоков, а не все последующие сохранённые префиксы.
Пример
Для A=[2,5,1,4,3,6,0,7]:sum(6)=T[6]+T[4]=9+12=21. После A[3]+=2 получаем 23.
Обновление идёт по i+=lowbit(i):3→4→8. Запрос идёт в обратную сторону покрытия:i-=lowbit(i),например 6→4→0.
Отличаем прибавку от присваивания
Базовое обновление добавляет delta к одному исходному элементу. Если требуется присвоить новое значение, сначала вычисляют разность нового и старого, затем добавляют именно её. Повторное добавление всего нового значения увеличило бы элемент сверх нужного. Для такой операции необходимо знать прежнее значение.
Сумму от l до r получают разностью двух префиксов:sum(r)−sum(l−1). В отличие от обычного статического массива префиксных сумм дерево удобно поддерживает изменения. Но этот конкретный вариант описывает сложение и разность; нельзя механически заменить сумму произвольной операцией, не проверив свойства блоков и возможность получить ответ отрезка из двух префиксов.
От чтения к действию
А теперь — вы
Частые вопросы
Почему не начинают обновление с индекса 0?
В принятой нумерации lowbit(0)=0,шаг не продвигается. Рабочие индексы начинаются с 1.
При присваивании надо добавить всё новое значение?
Нет. Нужна разность нового и старого значения; базовая операция является прибавкой.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Таблица минимумов: почему перекрытие блоков допустимо не всегда
Sparse Table для минимума на отрезке: блоки длины степени двойки, безопасное перекрытие и отличие от запроса суммы.
Открыть темуЛогическое и побитовое И: когда вычисляется правый операнд
Логическое and и побитовое&в Python: значение операнда, короткое вычисление и независимое сравнение двоичных разрядов.
Открыть тему