9.2 Дерево Фенвика¶

Дерево Фенвика (или Binary Indexed Tree, Fenwick Tree) можно рассматривать как динамическую версию массива префиксных сумм. Эта структура поддерживает две важные операции над массивом:

вычисление суммы на отрезке;
изменение одного элемента.

Обе операции выполняются за O(log n).

Главное преимущество дерева Фенвика в том, что оно позволяет быстро обновлять значения между запросами. В обычном массиве префиксных сумм после каждого изменения пришлось бы пересчитывать много значений заново, а здесь этого не требуется.

Идея структуры¶

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

Обозначим через p(k) наибольшую степень двойки, которая делит число k.

Тогда в массиве tree будем хранить такие суммы:

tree[k] = sum(k - p(k) + 1, k)

То есть ячейка tree[k] отвечает не за один элемент, а за некоторый хвостовой отрезок, который заканчивается в позиции k и имеет длину p(k).

Пример¶

Пусть исходный массив такой:

индекс:  1  2  3  4  5  6  7  8
значение: 2  1  5  3  4  6  2  7

Тогда дерево Фенвика будет хранить:

индекс:   1  2  3  4  5  6  7  8
tree:     2  3  5 11  4 10  2 30

Разберём несколько позиций:

tree[1] = 2, потому что p(1)=1, значит берём сумму на отрезке [1,1];
tree[2] = 2+1 = 3, потому что p(2)=2, значит это сумма на [1,2];
tree[3] = 5, потому что p(3)=1, значит это [3,3];
tree[4] = 2+1+5+3 = 11, потому что p(4)=4, значит это [1,4];
tree[6] = 4+6 = 10, потому что p(6)=2, значит это [5,6];
tree[8] = 2+1+5+3+4+6+2+7 = 30, потому что p(8)=8, значит это [1,8].

Какие отрезки покрывает дерево¶

Удобно думать так: каждая вершина отвечает за некоторый отрезок, длина которого равна младшему установленному биту её индекса.

Для массива выше получаются такие отрезки:

1 -> [1,1]
2 -> [1,2]
3 -> [3,3]
4 -> [1,4]
5 -> [5,5]
6 -> [5,6]
7 -> [7,7]
8 -> [1,8]

Как получить префиксную сумму¶

Сумму на префиксе sum(1, k) можно найти, если прыгать по индексам влево, каждый раз вычитая p(k).

Например, найдём сумму на префиксе до позиции 7:

sum(1,7) = tree[7] + tree[6] + tree[4]
         = 2 + 10 + 11
         = 23

Это действительно сумма элементов:

2 + 1 + 5 + 3 + 4 + 6 + 2 = 23

Почему так работает? Потому что отрезки:

tree[7] покрывает [7,7],
tree[6] покрывает [5,6],
tree[4] покрывает [1,4],

и вместе они как раз разбивают диапазон [1,7].

Как получить сумму на произвольном отрезке¶

Если нужна сумма на отрезке [a,b], то используется та же идея, что и с префиксными суммами:

sum(a,b) = sum(1,b) - sum(1,a-1)

Например:

sum(3,6) = sum(1,6) - sum(1,2)
         = 21 - 3
         = 18

Проверка по массиву:

5 + 3 + 4 + 6 = 18

Как выполняется обновление¶

Если значение массива в позиции k увеличилось на x, нужно поправить все ячейки tree, чьи отрезки содержат позицию k.

Например, если увеличить элемент в позиции 3 на 2, то изменятся:

tree[3], потому что оно хранит отрезок [3,3];
tree[4], потому что оно хранит [1,4];
tree[8], потому что оно хранит [1,8].

Именно поэтому обновление идёт прыжками вправо.

Битовая магия: почему работает `k & -k`¶

Ключевой факт:

p(k) = k & -k

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

Примеры:

6 = 110₂, тогда 6 & -6 = 2;
12 = 1100₂, тогда 12 & -12 = 4;
8 = 1000₂, тогда 8 & -8 = 8.

Именно это значение определяет длину отрезка, который хранится в tree[k].

Реализация¶

Ниже — стандартная реализация на C++.

int sum(int k) {
    int s = 0;
    while (k >= 1) {
        s += tree[k];
        k -= k & -k;
    }
    return s;
}

Эта функция возвращает сумму на префиксе [1,k].

void add(int k, int x) {
    while (k <= n) {
        tree[k] += x;
        k += k & -k;
    }
}

Эта функция увеличивает элемент массива в позиции k на x. Число x может быть и отрицательным, тогда это уменьшение.

Полный пример¶

#include <bits/stdc++.h>
using namespace std;

const int N = 200000;
int n;
int tree[N + 1];

int sum(int k) {
    int s = 0;
    while (k >= 1) {
        s += tree[k];
        k -= k & -k;
    }
    return s;
}

int sum(int l, int r) {
    return sum(r) - sum(l - 1);
}

void add(int k, int x) {
    while (k <= n) {
        tree[k] += x;
        k += k & -k;
    }
}

int main() {
    vector<int> a = {0, 2, 1, 5, 3, 4, 6, 2, 7}; // 1-индексация
    n = 8;

    for (int i = 1; i <= n; i++) {
        add(i, a[i]);
    }

    cout << sum(1, 7) << "\n"; // 23
    cout << sum(3, 6) << "\n"; // 18

    add(3, 2); // a[3] = 5 -> 7

    cout << sum(1, 7) << "\n"; // 25
    cout << sum(3, 6) << "\n"; // 20
}

Асимптотика¶

запрос суммы на префиксе: O(log n);
запрос суммы на отрезке: O(log n);
обновление одного элемента: O(log n);
память: O(n).

Когда дерево Фенвика особенно полезно¶

Эта структура хорошо подходит, когда:

нужно быстро считать суммы на отрезках;
между запросами происходят изменения отдельных элементов;
хочется более лёгкую и компактную альтернативу дереву отрезков.

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

Вывод¶

Дерево Фенвика — одна из самых полезных структур для задач на запросы по массиву. Оно компактное, быстро работает и легко пишется на соревновании. Главное, что нужно запомнить:

tree[k] хранит сумму на специальном хвостовом отрезке;
движение влево используется для запроса суммы;
движение вправо используется для обновления;
всё держится на выражении k & -k.