Дерево Фенвика: сумма на отрезке и обновления за O(log n)

Коротко

Дерево Фенвика (Binary Indexed Tree) решает задачу, где нужны и быстрые запросы суммы, и быстрые обновления.

Задача

Есть массив. Нужно уметь две вещи:

• узнать сумму на отрезке [l, r];
• изменить значение одного элемента.

Префиксные суммы отвечают на первый запрос за O(1), но после любого изменения их приходится пересчитывать целиком — O(n). Если обновлений много, это не работает.

Дерево Фенвика даёт логарифм на обе операции при минимуме кода — вся структура умещается в двадцать строк.

Идея: каждая ячейка отвечает за свой блок

Заведём массив tree того же размера. Ячейка tree[i] хранит не значение элемента, а сумму некоторого блока, заканчивающегося на позиции i.

Длина блока определяется хитро: это младший единичный бит числа i.

i = 1  (0001)  младший бит = 1  → блок длины 1: [1]
i = 2  (0010)  младший бит = 2  → блок длины 2: [1, 2]
i = 3  (0011)  младший бит = 1  → блок длины 1: [3]
i = 4  (0100)  младший бит = 4  → блок длины 4: [1, 2, 3, 4]
i = 6  (0110)  младший бит = 2  → блок длины 2: [5, 6]
i = 8  (1000)  младший бит = 8  → блок длины 8: [1..8]

Картинка покрытия:

индексы:  1   2   3   4   5   6   7   8
          |___|   |___|   |___|   |___|
          |_______|       |_______|
          |_______________|
          |_______________________|

Каждый уровень покрывает вдвое более длинные блоки. Любой префикс можно собрать из нескольких таких блоков — и их всегда не больше log n, потому что это разложение числа по двоичным разрядам.

Магия i & -i

Младший единичный бит извлекается одним выражением:

lowbit = i & -i

Почему это работает. В дополнительном коде -i это ~i + 1. Инверсия переворачивает все биты, прибавление единицы «всплывает» до первой единицы исходного числа. В итоге совпадает только один бит — самый младший единичный.

i  = 12 = 0000 1100
-i =    = 1111 0100
i & -i  = 0000 0100 = 4

Эта операция — сердце структуры. Ею мы и двигаемся по дереву.

Реализация на Python

class FenwickTree:
    def __init__(self, size: int) -> None:
        self.n = size
        self.tree = [0] * (size + 1)      # индексация с единицы

    def update(self, i: int, delta: int) -> None:
        """Прибавить delta к элементу с индексом i (1-based)."""
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i                   # к следующему блоку, который нас покрывает

    def prefix_sum(self, i: int) -> int:
        """Сумма элементов с 1 по i включительно."""
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i                   # к предыдущему непокрытому блоку
        return total

    def range_sum(self, left: int, right: int) -> int:
        """Сумма на отрезке [left, right] включительно."""
        return self.prefix_sum(right) - self.prefix_sum(left - 1)


ft = FenwickTree(8)
for i, value in enumerate([3, 2, -1, 6, 5, 4, -3, 3], start=1):
    ft.update(i, value)

print(ft.prefix_sum(5))     # 15  = 3+2-1+6+5
print(ft.range_sum(3, 6))   # 14  = -1+6+5+4

ft.update(3, 10)            # третий элемент вырос на 10
print(ft.range_sum(3, 6))   # 24

Два цикла отличаются знаком: при обновлении прибавляем младший бит, при запросе вычитаем. Это единственное, что нужно запомнить, — и это же самое частое место для ошибки.

Почему индексация с единицы

Ноль ломает всё: 0 & -0 равно нулю, и цикл в update зациклится, а в prefix_sum не начнётся. Поэтому массив tree делают на единицу длиннее, а нулевую ячейку не используют.

Если исходные данные с нуля, просто прибавляйте единицу при обращении:

ft.update(index + 1, value)

Разбор запроса по шагам

Посчитаем prefix_sum(7):

i = 7 (0111)  → берём tree[7], блок [7]
                i -= 1  →  i = 6

i = 6 (0110)  → берём tree[6], блок [5, 6]
                i -= 2  →  i = 4

i = 4 (0100)  → берём tree[4], блок [1, 2, 3, 4]
                i -= 4  →  i = 0

стоп. Сложили блоки [1..4] + [5,6] + [7] = [1..7]

Три обращения вместо семи. Число шагов равно количеству единиц в двоичной записи, то есть не больше log₂n.

Построение за O(n)

Наивно — n вызовов update, это O(n log n). Есть способ быстрее: заполнить массив значениями и «протолкнуть» каждую ячейку в родителя.

def build(values: list[int]) -> FenwickTree:
    n = len(values)
    ft = FenwickTree(n)
    ft.tree[1:] = values[:]              # копируем как есть

    for i in range(1, n + 1):
        parent = i + (i & -i)
        if parent <= n:
            ft.tree[parent] += ft.tree[i]

    return ft

Один проход, O(n).

Дерево Фенвика или дерево отрезков

Обе структуры решают похожие задачи, но с разными сильными сторонами.

Правило простое: нужна сумма и точечные обновления — Фенвик; нужно что-то сложнее — дерево отрезков.

Ограничение с минимумом принципиальное: структура опирается на обратимость операции (вычитание для суммы), а у минимума обратной операции нет.

Практические применения

Количество инверсий в массиве. Классическая задача: сколько пар i < j таких, что a[i] > a[j]. Идём справа налево, для каждого элемента спрашиваем «сколько уже встретилось меньших» и добавляем себя.

def count_inversions(arr: list[int]) -> int:
    # сжатие координат: значения → ранги 1..n
    ranks = {v: i + 1 for i, v in enumerate(sorted(set(arr)))}

    ft = FenwickTree(len(ranks))
    inversions = 0

    for value in reversed(arr):
        r = ranks[value]
        inversions += ft.prefix_sum(r - 1)   # сколько меньших уже справа
        ft.update(r, 1)

    return inversions


print(count_inversions([8, 4, 2, 1]))   # 6

Динамический рейтинг. Сколько игроков имеют счёт выше данного — при постоянно меняющихся очках.

Сумма на отрезке в задачах с обновлениями — прямое назначение.

Частые ошибки

Перепутанные знаки. += в обновлении, -= в запросе. Если поменять местами, код зациклится или выдаст мусор.

Индексация с нуля. Приводит к бесконечному циклу — самая частая ошибка новичков.

Присваивание вместо прибавления. update(i, x) прибавляет x, а не устанавливает значение. Чтобы установить, нужно передать разницу: update(i, new_value - old_value), и старое значение придётся хранить отдельно.

Попытка считать минимум. Структура для этого не приспособлена.

Что запомнить

• Дерево Фенвика даёт сумму на отрезке и обновление элемента за O(log n).
• Ячейка i хранит сумму блока длиной i & -i, заканчивающегося на позиции i.
• Обновление идёт вверх с i += i & -i, запрос вниз с i -= i & -i.
• Индексация обязательно с единицы.
• Работает только с обратимыми операциями: сумма, XOR. Для минимума нужно дерево отрезков.