Дерево Фенвика в массиве: битовые переходы, код и сравнение с сегментным деревом

Дерево Фенвика (Fenwick tree), известное также как Binary Indexed Tree или BIT, хранит префиксные суммы в обычном плоском массиве на n+1 элементов и выполняет точечное обновление и запрос суммы за O(log n). Ни узлов с указателями, ни объектов, ни рекурсии внутри нет: связи между индексами задают две битовые формулы.

Короткий ответ на главный вопрос: дерево Фенвика — это структура индексов, а не дерево узлов. Массив остаётся линейным, а иерархия возникает только в момент чтения, когда каждый индекс i отвечает за диапазон элементов (i - lowbit(i) + 1) .. i. Это принципиально отличает структуру от кучи и сегментного дерева, где потомки вычисляются как 2i и 2i+1.

Практическая выгода видна сразу: там, где нужны префиксные суммы и точечные правки счётчиков, дерево Фенвика даёт тот же O(log n) на операцию, что и сегментное дерево, но укладывается в память O(n) вместо O(4n) и в десяток строк кода. Ценой становится узкий набор поддерживаемых операций, о котором говорим в отдельном разделе.

Что такое дерево Фенвика и почему оно живёт в массиве

Структура состоит из одного массива tree длиной n+1. Индексация начинается с единицы, элемент tree[0] не используется. Каждый tree[i] хранит агрегат (в базовом варианте — сумму) по непрерывному диапазону исходного массива a, и длина этого диапазона равна младшему установленному биту индекса i.

Формально tree[i] = sum(a[i - lowbit(i) + 1 .. i]), где lowbit(i) = i & -i. Для массива из 8 элементов индексы идут от 1 до 8, и каждый узел покрывает диапазон длиной lowbit(i): tree[1] отвечает за a[1], tree[2] — за a[1] + a[2], tree[4] — за сумму a[1] .. a[4], tree[8] — за сумму всех восьми элементов.

Индексация с нуля ломает всю схему: lowbit(0) равен нулю, и переход i += i & -i перестаёт менять индекс. Поэтому либо держите массив tree размером n+1 и работайте с индексами 1..n, либо при хранении исходных данных с нуля добавляйте единицу на входе в каждую операцию.

Дерево Фенвика vs классическое дерево в массиве

Классическое дерево в массиве, будь то двоичная куча или сегментное дерево, держит явные связи между узлами. В куче левый потомок узла i вычисляется как 2i, правый как 2i+1, а родитель как floor(i/2). Обход идёт сверху вниз и снизу вверх по этой иерархии, и любой узел знает своих соседей по арифметике индексов.

В дереве Фенвика родителей и детей нет вовсе. Переходы задают две операции над младшим битом: i + lowbit(i) уводит к следующему индексу, который накрывает текущий диапазон (используется при обновлении), а i - lowbit(i) срезает младший бит и ведёт к предыдущему диапазону (используется при запросе).

Посмотрите на конкретику. Для i = 6 (двоичное 110) lowbit равен 2, значит tree[6] покрывает элементы 5..6. Для i = 8 (двоичное 1000) lowbit равен 8, поэтому tree[8] накрывает диапазон 1..8. Диапазоны перекрываются: элемент a[5] попадает одновременно в tree[5], tree[6] и tree[8]. Именно перекрытие, а не иерархия, обеспечивает ответ на запрос за логарифм.

Битовые переходы: как lowbit управляет индексами

Функция lowbit(i) = i & -i возвращает значение младшего установленного бита. Числа здесь маленькие и предсказуемые: lowbit(6) = 2, lowbit(7) = 1, lowbit(8) = 8. Таблица ниже показывает полную картину для n = 8 и заодно служит шпаргалкой при отладке.

Все переходы сводятся к арифметике над индексом. Рекурсия не нужна, стек не растёт, а каждая операция выполняется за число шагов, равное количеству единичных битов в индексе, то есть не больше log n + 1.

Почему i & -i даёт младший установленный бит

Работает это благодаря дополнительному коду. Отрицательное число -i получается инверсией всех битов i и прибавлением единицы. Инверсия превращает младший установленный бит в ноль, а все биты правее него в единицы; прибавление единицы снова делает младший бит единицей и обнуляет всё правее. После побитового И с исходным i остаётся ровно один бит, тот самый младший.

Разберём на i = 6. В 64-битном представлении 6 это ...00000110, тогда -6 это ...11111010. Побитовое И даёт ...00000010, то есть 2. Никакой магии, чистая арифметика двоичного представления.

Оговорка про типы: в C и C++ переполнение знаковых целых является неопределённым поведением, поэтому отрицание большого индекса, приводящее к переполнению, тоже небезопасно. Держите индексы в разумных пределах (характерные значения до 2^31). Для беззнаковых типов переполнение определено как взятие остатка по модулю 2^N, и lowbit считается корректно. В Python целые произвольной длины и в Java с типом int конструкция i & -i работает без дополнительных условий.

Операции update и prefix_sum: формулы и готовый код

Две операции покрывают весь базовый набор задач. Обновление прибавляет дельту к одному элементу и поднимается вверх по индексам, а запрос собирает сумму префикса, спускаясь вниз.

update(i, delta):
    while i <= n:
        tree[i] += delta
        i += i & -i

prefix_sum(i):
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s

Сумма на отрезке [l, r] считается как разность двух префиксов: prefix_sum(r) - prefix_sum(l - 1). Обе операции дают O(log n). Построение дерева из готового массива можно выполнить за O(n) с помощью оптимизированного метода, а не только за O(n log n) последовательными обновлениями.

Реализация на Python с построением за O(n):

class Fenwick:
    def __init__(self, a):
        self.n = len(a)
        self.tree = [0] * (self.n + 1)
        for i, x in enumerate(a, start=1):
            self.tree[i] += x
            j = i + (i & -i)
            if j <= self.n:
                self.tree[j] += self.tree[i]

    def update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i

    def prefix_sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def range_sum(self, l, r):
        return self.prefix_sum(r) - self.prefix_sum(l - 1)

Вариант на C++ с 64-битными суммами, чтобы не ловить переполнение на больших массивах:

int n;
std::vector<long long> tree;  // размер n + 1

void update(int i, long long delta) {
    for (; i <= n; i += i & -i) tree[i] += delta;
}

long long prefix_sum(int i) {
    long long s = 0;
    for (; i > 0; i -= i & -i) s += tree[i];
    return s;
}

Для сервисов на Go, где счётчики метрик часто живут в памяти процесса, тот же алгоритм выглядит так:

type Fenwick struct {
    n    int
    tree []int64
}

func (f *Fenwick) Update(i int, delta int64) {
    for ; i <= f.n; i += i & -i {
        f.tree[i] += delta
    }
}

func (f *Fenwick) PrefixSum(i int) int64 {
    var s int64
    for ; i > 0; i -= i & -i {
        s += f.tree[i]
    }
    return s
}

Пошаговый пример: строим дерево для массива из 8 элементов

Возьмём a = [3, 2, -1, 6, 5, 4, -3, 3] и построим дерево вручную. Раскладка по диапазонам из таблицы выше даёт такие значения:

Запрос prefix_sum(6) идёт по цепочке 6, затем 6 - lowbit(6) = 4, затем 4 - lowbit(4) = 0. Складываем tree[6] + tree[4] = 9 + 10 = 19. Проверка по исходным данным: 3 + 2 - 1 + 6 + 5 + 4 = 19, сходится.

Теперь обновление update(3, +5). Цепочка индексов: 3, затем 3 + 1 = 4, затем 4 + 4 = 8, затем 16 выходит за n = 8 и цикл останавливается. Получаем tree[3] = 4, tree[4] = 15, tree[8] = 24. Повторный prefix_sum(7) собирает -3 (индекс 7), 9 (индекс 6), 15 (индекс 4) и даёт 21, что совпадает с новой суммой элементов с первого по седьмой.

Где граница между деревом и структурой индексов

Классическое дерево — это иерархия узлов с явными связями: либо указателями, либо вычисляемыми индексами 2i и 2i+1. Дерево Фенвика — это массив, где каждый индекс хранит агрегат по диапазону, а связи заданы битовыми операциями. Родителя и детей здесь нет, есть перекрывающиеся диапазоны фиксированной формы.

Путаница возникает из-за названия. Слово дерево намекает на узлы и обходы, а по факту вы получаете индексную адресацию: чтобы понять, какие элементы входят в tree[i], достаточно вычислить границу диапазона, а чтобы перейти к следующему диапазону, хватает одной битовой операции.

Почему это важно для практики

Осознание того, что перед вами структура индексов, экономит время в трёх типичных ситуациях. Во-первых, вы не ищете в коде указатели и рекурсивные вызовы: их там просто нет. Во-вторых, отладка сводится к печати lowbit и границ диапазона, а не к трассировке глубокого дерева. В-третьих, выбор между структурой и сегментным деревом становится осознанным, а не интуитивным.

Ограничение вытекает из той же природы. Диапазонный агрегат восстанавливается вычитанием префиксных сумм: сумма на отрезке [L, R] вычисляется как prefix(R) - prefix(L - 1). Поэтому базовая схема работает для обратимых операций: суммы, XOR, произведения ненулевых чисел. Произвольный минимум или максимум на отрезке так не получить — сегментное дерево здесь обязательно.

Дерево Фенвика vs сегментное дерево: что выбрать

Обе структуры дают O(log n) на операцию, но расходятся в памяти, объёме кода и наборе поддерживаемых запросов.

Правило простое. Нужны префиксные суммы, суммы на отрезке и точечные правки счётчиков — берите дерево Фенвика. Нужны минимум или максимум, массовые обновления диапазона или нестандартные запросы — берите сегментное дерево.

Двумерный вариант BIT выполняет точечные обновления и запросы префиксных сумм подматриц за O(log N · log M) и применяется в задачах подсчёта точек на прямоугольнике и в обработке матриц. В повседневной работе DevOps-инженера такие сценарии редки: чаще это одномерные счётчики и накопительная статистика по времени.

Когда дерево Фенвика не оправдано

• Поиск минимума или максимума на произвольном отрезке: операция не восстанавливается вычитанием префиксов, нужна другая структура.
• Массовые обновления диапазона (прибавить k ко всем элементам отрезка): в базовой схеме не поддерживаются, приходится заводить второе дерево и усложнять код.
• Некоммутативные операции: агрегат диапазона нельзя корректно собрать из перекрывающихся кусков, порядок нарушится.
• Запросы вида k-й порядковой статистики и сложные условия поиска: сегментное дерево с спуском по узлам гибче.

Живой пример из инфраструктурных задач. Если вы считаете количество запросов к API за интервал и обновляете счётчики по мере поступления событий, дерево Фенвика подходит идеально. Если же требуется найти минимальную задержку на отрезке времени, нужна структура с поддержкой минимума.

Типичные ошибки при работе с битовыми переходами

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

1. Индексация с нуля. lowbit(0) равен нулю, и цикл обновления становится бесконечным.
2. Выход за границы массива при обновлении, когда i + lowbit(i) превышает n, а условие цикла задано неверно.
3. Неверный размер массива tree: нужен n + 1, иначе последний элемент теряется.
4. Путаница между индексом в исходном массиве и индексом в дереве при работе со сдвинутой нумерацией.
5. Переполнение при отрицании больших индексов в языках с фиксированной разрядностью знаковых типов.

Ошибка с нулевым индексом выглядит так и никогда не завершается:

i = 0
while i <= n:
    tree[i] += delta
    i += i & -i   # lowbit(0) == 0, индекс не меняется

Исправление — хранить дерево с индексами от 1 и передавать позицию как idx + 1:

def update(self, idx, delta):
    i = idx + 1          # перевод в 1-based
    while i <= self.n:
        self.tree[i] += delta
        i += i & -i

Для отладки держите под рукой два приёма. Печатайте lowbit и границы диапазона на каждом шаге цикла, тогда сразу видно, куда уходит индекс. Прогоняйте тест на маленьком массиве из 4-8 элементов с ручным пересчётом сумм: расхождение проявляется на первом же запросе.

Чек-лист выбора структуры под задачу

Начните с проверки двух условий: операция обратима и запросы сводятся к префиксу или отрезку. Если оба выполняются, дерево Фенвика даст компактный код и память n+1. Как только появляется минимум, максимум или массовые правки диапазона, переходите на сегментное дерево и не пытайтесь расширять BIT костылями.

Источники

• Binary Indexed Tree or Fenwick Tree — GeeksforGeeks
• Fenwick Tree — Algorithms for Competitive Programming
• Дерево Фенвика — Викиконспекты
• Многомерное дерево Фенвика — Викиконспекты
• Union-Find, Trie, Fenwick Tree & Segment Tree — Wasil Zafar
• Why is unsigned integer overflow defined behavior but signed integer overflow is not — Stack Overflow
• C++ programmer's guide to undefined behavior: part 2 of 11 — PVS-Studio
• 2D Fenwick Tree (Binary Indexed Tree) — Submatrix Sums in O(log²)