Определение

Дерево Фенвика - простая в реализация, быстрая в работе, но совершенно неочевидная в идее структура данных, позволяющая находить сумму на префиксе и изменять отдельные элементы за \(O(\log N)\). Несмотря на одинаковую сложность, дерево Фенвика работает значительно быстрее дерева отрезков.

В этой лекции не будет приводится точный принцип работы дерева Фенвика, будут приведены только реализация и способы использования.

Алгоритм

Дерево Фенвика, хотя и является по идее деревом, представляется в виде массива \(f\), в котором \(f[i]\) - сумма элементов от \(F(i)\) до \(i\).

Функция \(F(x)\) связана с битовым представлением числа \(x\). Её можно описать следующим образом: \(F(x)\) заменяет группу единичных битов, находящихся в конце числа (младших) на нули. Если \(x\) заканчивается на нулевой бит, то \(F(x) = x\). С помощью битовых операций \(F(x)\) записывается следующим образом:

\[F(x) = x\ and\ (x + 1)\]

Значит, функцию нахождения суммы на промежутке \([0; x]\) можно реализовать следующим образом:

1
2
3
4
5
6
7
8
9

int sum(int x) {
    int result = 0;

    for (; x >= 0; x = (x & (x + 1)) - 1) {
        result += f[x];
    }

    return result;
}

Осталось понять, как обновлять значения дерева Фенвика при изменении элемента. При изменении элемента \(i\) нужно обновить все \(f[j]\), где \(F(j) \le i \le j\). Оказывается, последовательность \(j\) выглядит следующим образом:

\[j_0 = i \\ j_i = j_{i - 1}\ or\ (j_{i - 1} + 1)\]

Значит, обновление элемента реализуется следующим образом:

1
2
3
4
5
6
7
8

//Увеличить a[idx] на delta
void increase(int idx, int delta) {
    a[idx] += delta;

    for (; idx < n; idx |= idx + 1) {
        f[idx] += delta;
    }
}

Реализация

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include <bits/stdc++.h>

using namespace std;

int n;
int a[100000];  //массив
int f[100000];  //дерево Фенвика

//сумма элементов от 0 до x
int sum(int x) {
    int result = 0;

    for (; x >= 0; x = (x & (x + 1)) - 1) {
        result += f[x];
    }

    return result;
}

//сумма элементов от l до r
int sum(int l, int r) {
    if (l) {
        return sum(r) - sum(l - 1);
    } else {
        return sum(r);
    }
}

//увеличение a[idx] на delta
void increase(int idx, int delta) {
    a[idx] += delta;

    for (; idx < n; idx |= idx + 1) {
        f[idx] += delta;
    }
}

int main() {
    cin >> n;

    for (int i = 0; i < n; i++) {    //ввод массива и заполнение дерева Фенвика
        int t;
        cin >> t;
        increase(i, t);
    }

    //Можем обрабатывать запросы
}

Дерево Фенвика для поиска минимума/максимума на префиксе

С помощью дерева Фенвика также можно поддерживать минимумы/максимумы на префиксах, но поддерживаемые операции такого дерева значительно ограничиваются:

  • По значениям минимума/максимума на префиксе невозможно установить значение на произвольном отрезке.

  • Возможно только уменьшение (дерево для поиска минимума)/увеличение (дерево для поиска максимума) элементов.

Реализация почти совпадает с реализацией для поиска суммы:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <bits/stdc++.h>

using namespace std;

int n;
int a[100000];  //массив
int f[100000];  //дерево Фенвика

//минимум среди элементов от 0 до x
int get_min(int x) {
    int result = INT_MAX;

    for (; x >= 0; x = (x & (x + 1)) - 1) {
        result = min(result, f[x]);
    }

    return result;
}

//присваивание a[idx] = val (val <= a[idx])
void assign(int idx, int val) {
    a[idx] = val;

    for (; idx < n; idx |= idx + 1) {
        f[idx] = min(f[idx], val);
    }
}

int main() {
    cin >> n;

    for (int i = 0; i < n; i++) {       //Изначально принимаем все значения в дереве
        f[i] = INT_MAX;                 //равными бесконечности, так как далее их можно
    }                                   //только уменьшать.

    for (int i = 0; i < n; i++) {    //ввод массива и заполнение дерева Фенвика
        int t;
        cin >> t;
        assign(i, t);
    }

    //Можем обрабатывать запросы.
}

Решение задачи о наибольшей возрастающей последовательности с помощью дерева Фенвика на максимумы

Эта задача уже разбиралась в лекции про динамическое программирование, и мы упоминали, что её можно решать за \(O(N \log N)\) с помощью дерева Фенвика. Разберём это решение.

Для решения важно ограничение на элементы последовательности. Если \(a_i \le 10^6\), то задачу можно решать с помощью дерева Фенвика, иначе, необходимо сначала “сжать” значения (заменить каждое значение на его индекс в порядке сортировки).

Идея решения достаточно простая: будем идти по последовательности слева направо, поддерживая массив \(f\), где \(f[i]\) - длина наибольшей возрастающей подпоследовательности, заканчивающейся на число \(i\). Изначально \(f[i] = 0\) для всех \(i\).

При обработке очередного элемента, пытаемся улучшить длину подпоследовательности, на него заканчивающейся. Для этого мы можем продолжить последовательность любой меньшей длины, или начать новую. В виде формулы это можно записать так (текущий элемент равен \(x\)):

\[f[x] = \max(f[x], \max\limits_{i = 0}^{x - 1} f[i] + 1)\]

Заметим в формуле максимум на префиксе. Если находить его с помощью дерева Фенвика за \(O(\log N)\), можно решать задачу за \(O(N \log N)\).

Ответом на задачу будет максимум по всем \(f\).

Реализация на C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include <bits/stdc++.h>

using namespace std;

int n;
int seq[100000];  //последовательность

int a[1000001];  //массив, соответствующий дереву Фенвика
int f[1000001];  //дерево Фенвика

int get_max(int x) {
    int result = INT_MIN;

    for (; x >= 0; x = (x & (x + 1)) - 1) {
        result = max(result, f[x]);
    }

    return result;
}

//(val >= a[idx])
void assign(int idx, int val) {
    a[idx] = val;

    for (; idx <= 1000000; idx |= idx + 1) {
        f[idx] = max(f[idx], val);
    }
}

int main() {
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> seq[i];
    }

    for (int i = 0; i < n; i++) {
        int x = seq[i];
        int prev_max = get_max(x - 1);  //максимальная длина, которую можно продолжить

        if (prev_max + 1 > a[x]) {
            assign(x, prev_max + 1);
        }
    }

    int ans = get_max(1000000);
    cout << ans << endl;
}

Обобщение дерева Фенвика на несколько измерений

Ещё одно преимущество дерева Фенвика перед деревом отрезков - абсолютно тривиальный способ обобщения на несколько измерений (сложность запроса для \(K\)-мерного дерева Фенвика равна \(O(2^k * \log^k N)\)). В качестве примера приведём реализацию двумерного дерева Фенвика для нахождения суммы на “префиксе” матрицы:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#include <bits/stdc++.h>

using namespace std;

int n, m;
int a[1000][1000];  //матрица
int f[1000][1000];  //дерево Фенвика

//сумма элементов от (0, 0) до (x, y)
int sum(int x, int y) {
    if (x < 0 || y < 0) {
        return 0;
    }

    int result = 0;

    for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
        for (int j = y; j >= 0; j = (j & (j + 1)) - 1) {
            result += f[i][j];
        }
    }

    return result;
}

//сумма элементов от (x1, y1) до (x2, y2)
//(разбирается в лекции про префиксные суммы)
int sum(int x1, int y1, int x2, int y2) {
    return sum(x2, y2)
         - sum(x1 - 1, y2)
         - sum(x2, y1 - 1)
         + sum(x1 - 1, y1 - 1);
}

//увеличение a[x][y] на delta
void increase(int x, int y, int delta) {
    a[x][y] += delta;

    for (int i = x; i < n; i |= i + 1) {
        for (int j = y; j < m; j |= j + 1) {
            f[i][j] += delta;
        }
    }
}

int main() {
    cin >> n >> m;

    for (int i = 0; i < n; i++) {    //ввод массива и заполнение дерева Фенвика
        for (int j = 0; j < m; j++) {
            int t;
            cin >> t;
            increase(i, j, t);
        }
    }

    //Можем обрабатывать запросы
}