Дерево Фенвика (Binary Indexed Tree)

Коротко: Дерево Фенвика хранит массив чисел так, что и изменение значения, и префиксные суммы выполняются за O(log n).

Подробнее: Это особенно компактная альтернатива дереву отрезков, когда нужны только суммы (или похожие обратимые операции). Дерево живёт в простом массиве, а вычисление индексов использует младший установленный бит.

Подробности

• Идея: Позиция i хранит сумму отрезка, длина которого равна наибольшей степени двойки, делящей i.
• Запрос: Префиксная сумма до i: прибавить значение, затем i -= i & -i, пока i не станет 0.
• Изменение: Изменить значение на d: прибавить в i, затем i += i & -i, пока i не превысит размер.
• Сумма на отрезке: сумма(r) - сумма(l-1).
• Построение: Возможно за O(n), память — всего n чисел.
• Ограничения: Не каждая операция обратима. Минимум на отрезке поэтому обычно требует дерева отрезков.

См. также: O-нотация