Информатика · объяснение и практика

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

Дерево Фенвика для суммы: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). В отличие от обычного статического массива префиксных сумм дерево удобно поддерживает изменения. Но этот конкретный вариант описывает сложение и разность; нельзя механически заменить сумму произвольной операцией, не проверив свойства блоков и возможность получить ответ отрезка из двух префиксов.

От чтения к действию

А теперь — вы

Элемент имел значение 7,его нужно заменить на 10. Какую delta передать операции прибавления дерева Фенвика?

Частые вопросы

Почему не начинают обновление с индекса 0?

В принятой нумерации lowbit(0)=0,шаг не продвигается. Рабочие индексы начинаются с 1.

При присваивании надо добавить всё новое значение?

Нет. Нужна разность нового и старого значения; базовая операция является прибавкой.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться