Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Введение

Дерево Фенвика - структура данных, которая позволяет выполнять обратимые, коммутативные, ассоциативные операции на отрезке.

Пример операций:

1. Обратимые операции: $a ^ b$
2. Коммутативные операции: $a + b = b + a$
3. Ассоциативные операции: $a * (b * c) = (a * b) * c$

Также позволяет изменять любое значение в массиве.

---

Пример использования

Задача: Найти сумму последовательно расположенных элементов от индекса $L$ до индекса $R$. Массив $А = [4, 8, 15, 16, 23, 42, 8, 4, 16, 20]$, ищем сумму на отрезке $[2; 7]$.

Решение 1

Пройдем циклом с предусловием по массиву, с условием $L \le R$. На каждом шаге прибавляем сумму в результирующую переменную и прибавляем к $L$ один.

В результате, получили сумму на отрезке $[2, 7]$. Этот массив позволяет быстро обновлять элементы в исходном массиве, однако сложность поиска суммы в нем линейна. Поэтому этот способ решения может быть неподходящим, если требуется частое вычисление суммы.

Вычислительная сложность

Поиск суммы - $О(n)$ Препроцесс - $O(1)$ Обновление элемента массива - $O(1)$, где $n$ - длина изначального массива.

---

Решение 2

Создадим новый массив $PR$, в котором будет хранится сумма от 0 до $i$-ой ячейки исходного массива (массив префикс сумм). Благодаря такому массиву, сумма равна $PR[R] - PR[L-1]$ .

В результате, сумма на отрезке $[2, 7]$ равна $PR[7] - PR[1]$ = 107. Главный минус данного способа - обновление элемента имеет вычислительную сложность $O(n)$, потому что нужно обновить сумму ячейки и всех ячеек правее. Поэтому, если нужно часто обновлять значения, то способ хуже, чем решение 1.

## Вычислительная сложность

Поиск суммы - $О(1)$ Препроцесс - $O(n)$ Обновление элемента массива - $O(n)$, где $n$ - длина изначального массива.

---

Решение 3

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

Этап 1. Построить дерево Фенвика

Дерево Фенвика - массив, который хранит префикс сумму от $i$-ого до $j$-ого элемента, где $j$ - индекс текущего элемента.

Как найти $i$ индекс, с которого будем считать префикс сумму?

Предположим, что длина массива равна 16. Сначала, переведём числа индексов $j$ в двоичную систему:

Чтобы получить индекс $i$, нужно справа налево заменить 1 на 0, до первого встречного нуля.

Можно это реализовать через цикл, но проще и быстрее через битовую формулу. Формула индекса $i$ можно через битовые операции: $i = j \& (j + 1)$, где $i$ - индекс от которого будет просчитана префикс сумма, $j$ - индекс до которого будет просчитана префикс сумма, & - побитовое И.

На рисунке показана табличка элементов, на вертикальной оси - индексы элементов исходного массива, на горизонтальной - элементы дерева Фенвика, выделены цветом - префикс суммы от $i$ до $j$ соответственно.

Чтобы построить дерево Фенвика, нужно сначала завести массив из нулей, длина которого равна исходному. Затем, в $i$ ячейку добавить $i$ элемент исходного массива. После этого пересчитать индекс на новый. Например, элемент $i$ = 1 исходного массива нужно прибавить к 1, 3, 7, 15 ячейке дерева Фенвика, это видно на табличке. Элемент $i$ = 8 исходного массива нужно прибавить к 8, 9, 11, 15 ячейке дерева Фенвика. Если эти числа перевести в двоичную систему, то получим такие числа:

То есть, чтобы получить новый индекс $j$, нужно справа налево заменить первый встречный 0 на 1.

Формула индекса $j$ через битовые операции: $j = i | (i+1)$, где $i$ - индекс массива, $j$ - новый индекс массива, | - побитовое ИЛИ. Формулу нужно применять для всех элементов массива, пока $j < n$, где $n$ - размер исходного массива.

Также этот способ можно использовать, чтобы изменить любой элемент на другой, так как заполнение дерева Фенвика по сути изменяет 0 на другое значение.

Псевдокод функции для построения дерева Фенвика и изменения элемента в дереве Фенвика:

функция изменения элемента в дереве Фенвика(дерево Фенвика, индекс i, элемент A[i]):
    delta <- элемент A[i]
    Пока индекс i меньше, чем размер массива дерева_Фенвика:
        дерево_Фенвика[i] = дерево_Фенвика[i] + delta
        i = i | (i + 1)
    вернуть обновлённое дерево_Фенвика
    
функция построения дерева Фенвика(сходный массив А):
    дерево_Фенвика <- массив длины А, заполненный нулями
    Для каждого i элемента из массива А:
        Изменить элемент i в дереве_Фенвика на A[i]
    вернуть дерево_Фенвика

Например, для исходного массива $А$, дерево Фенвика равно:

Этап 2. Запрос к дереву Фенвика

В этом примере будем искать сумму. Чтобы найти сумму на промежутке от $L$ до $R$, нужно собрать префикс суммы с 0 до $R$, затем из этой суммы вычесть суммы от 0 до $L$ - 1. Пусть размер массива равен 16, $L$ = 5, $R$ = 13.

Сумма $sum1$ от 0 до $R$, где $R$ = 13, состоит из префикс сумм $[12,13], [8, 11], [0, 7]$. Сумма $sum2$ от 0 до $L$ - 1, где $L$ = 5, состоит из префикс сумм $[4, 4], [0, 3]$. Если из $sum1$ вычесть $sum2$, то получим как раз сумму на промежутке от $L$ до $R$.

Как узнать, какие суммы нужно взять?

Первая префикс сумма лежит в дереве Фенвика в промежутке от $i$ до $j$, где $j$ = $R$, а $i = j \& (j + 1)$. Следующий промежуток лежит на индексах $j$ = $i$ - 1, $i = j \& (j + 1)$. Так пересчитываются индексы, пока $i$ > 0.

Итого, чтобы собрать сумму sum1 от 0 до $R$, нужно взять сумму в дереве Фенвика по индексу $j$ = $R$, затем пересчитать индекс $j = i - 1 = (j \& (j + 1)) - 1$. Так индекс попадает в следующую префикс сумму, которая нужна для sum1, берём сумму по новому индексу из дерева Фенвика. Берём суммы, пока $j$ > 0. Для второй суммы $sum2$ делаем аналогично. Результирующая сумма равна $sum1$ - $sum2$.

Псевдокод функции для расчёта суммы на промежутке в дереве Фенвика:

Функция расчёта суммы на промежутке от 0 до k(дерево Фенвика, правая граница k):
    сумма <- ноль
    Пока правая граница k больше или равна 0:
        К сумме прибавить дерево_Фенвика[k]
        k = (k & (k + 1)) - 1
    Вернуть сумму

Функция расчёта суммы на промежутке от L до R(дерево Фенвика, левая граница L, правая граница R):
    сумма <- Из суммы на промежутке от 0 до R вычесть сумму на промежутке от 0 до L-1
    Вернуть сумму

Вычислительная сложность

Поиск суммы - $О(log(n))$ Препроцесс - $О(n * log(n))$ Обновление элемента массива - $O(log(n))$, где $n$ - длина изначального массива.

---

Псевдокод

функция изменения элемента в дереве_Фенвика(дерево Фенвика Fenwick, индекс i, элемент A[i]):
    delta <- элемент A[i]
    Пока i меньше, чем размер массива дерева_Фенвика:
        дерево_Фенвика[i] = дерево_Фенвика[i] + delta
        i = i | (i + 1)
    вернуть обновлённое дерево Фенвика

функция построения дерева Фенвика(сходный массив А):
    дерево_Фенвика <- массив длины А, заполненный нулями
    Для каждого i элемента из массива А:
        Изменить элемент i в дереве_Фенвика на A[i]
    вернуть дерево_Фенвика

Функция расчёта суммы на промежутке от 0 до k(дерево Фенвика, правая граница k):
    Ввод: дерево Фенвика Fenwick, правая граница k
    Вывод: сумма на промежутке от 0 до k
    
    сумма <- ноль
    Пока правая граница k больше или равна 0:
        сумма += дерево_Фенвика[k]
        k = (k & (k + 1)) - 1
    Вернуть сумму

Функция расчёта суммы на промежутке от L до R(дерево Фенвика, левая граница L, правая граница R):
    сумма <- Из суммы на промежутке от 0 до R вычесть сумму на промежутке от 0 до L-1
    Вернуть сумму

---

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

Аннотация:
A - исходный массив
n - длинна массива
FenwickTree - дерево Фенвика
modify - функция изменения элементов в массиве, на который опирается дерево Фенвика
temp_sum - функция, которая возвращает префиксную сумму элементов дерева Фенвика
res - итоговая сумма
sum - функция суммы элементов массива на заданном отрезке
l - левая граница отрезка
r - правая граница отрезка
sum1 - сумма на промежутке от 0 до r
sum2 - сумма на промежутке от 0 до l-1
build - функция инициализации дерева Фенвика

A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
n = len(A)
FenwickTree = []

for i in range(0, n):
    FenwickTree.append(0)
  
def modify(index, delta):
    while index < n:
        FenwickTree[index] += delta;
        index = index | (index + 1)

def temp_sum(index):
    res = 0
    while index >= 0:
        res += FenwickTree[index]
        index = (index & (index + 1)) - 1
    return res
  
def sum(l, r):
    sum1 = temp_sum(r)
    sum2 = temp_sum(l - 1)
    res = sum1 - sum2
    return res

def build():
    for i in range(0, n):
        modify(i, A[i])  

---

Олимпиадная реализация на C++

Аннотация:
A - исходный массив
n - длинна массива
FT - дерево Фенвика
modify - функция изменения элементов в массиве, на который опирается дерево Фенвика
build - функция инициализации дерева Фенвика
temp_sum - функция, которая возвращает префиксную сумму элементов дерева Фенвика
res - итоговая сумма
sum - функция суммирования элементов массива на заданном отрезке
l - левая граница отрезка
r - правая граница отрезка

vector<int> A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int n = A.size();
vector<int> FT(n, 0);

void modify(int index, int delta) {
  while (index < n) {
    FT[index] += delta;
    index = index | (index + 1);
  }
}

void build() {
  for (int i = 0; i < n; i++) {
    modify(i, A[i]);
  }
}

int temp_sum(int index) {
  int res = 0;
  while (index >= 0) {
    res += FT[index];
    index = (index & (index + 1)) - 1;
  }
  return res;
}

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

---

Продуктовая реализация на C++

Реализация интерфейса

Аннотация:
template - шаблон функции
typename TValue - шаблонный тип данных параметра
FenwickTree - шаблонный класс дерева Фенвика
Fenwick - дерево Фенвика
temp_sum - функция, которая возвращает префиксную сумму элементов дерева Фенвика
FenwickTree() - конструктор дерева Фенвика
A - исходный массив
build - функция, которая строит дерево Фенвика
modify - функция изменения элементов в массиве, на который опирается дерево Фенвика
sum - функция суммирования элементов массива на заданном отрезке
l - левая граница отрезка
r - правая граница отрезка

#pragma once
#include <iostream>
#include <vector>
using namespace std;

template <typename TValue>
class FenwickTree {
  vector<TValue> Fenwick;
  TValue temp_sum(long long index);

 public:
  FenwickTree();
  FenwickTree(vector<TValue> &A);
  void build(vector<TValue> &A);
  void modify(long long index, TValue delta);
  TValue sum(long long l, long long r);
}

Реализация дерева Фенвика

Аннотация:
template - шаблон функции
typename TValue - шаблонный тип данных параметра
FenwickTree - шаблонный класс дерева Фенвика
modify - функция изменения элементов в массиве, на который опирается дерево Фенвика
Fenwick - дерево Фенвика
n - длинна массива
build - функция, которая строит дерево Фенвика
A - исходный массив
FenwickTree() - конструктор дерева Фенвика
temp_sum - функция, которая возвращает префиксную сумму элементов дерева Фенвика
res - итоговая сумма
sum - функция суммирования элементов массива на заданном отрезке
l - левая граница отрезка
r - правая граница отрезка
sum1 - сумма на промежутке от 0 до r
sum2 - сумма на промежутке от 0 до l-1

#pragma once
#include <cmath>
#include <iostream>
#include <vector>

using namespace std;

template <typename TValue>
void FenwickTree<TValue>::modify(long long index, TValue delta) {
  long long n = Fenwick.size();
  while (index < n) {
    Fenwick[index] += delta;
    index = index | (index + 1);
  }
}

template <typename TValue>
void FenwickTree<TValue>::build(vector<TValue> &A) {
  long long n = A.size();
  Fenwick = vector<TValue>(n);
  for (long long i = 0; i < n; i++) {
    modify(i, A[i]);
  }
}

template <typename TValue>
FenwickTree<TValue>::FenwickTree(vector<TValue> &A) {
  build(A);
}

template <typename TValue>
FenwickTree<TValue>::FenwickTree() {}

template <typename TValue>
TValue FenwickTree<TValue>::temp_sum(long long index) {
  TValue res = 0;
  while (index >= 0) {
    res += Fenwick[index];
    index = (index & (index + 1)) - 1;
  }
  return res;
}

template <typename TValue>
TValue FenwickTree<TValue>::sum(long long l, long long r) {
  TValue sum1 = temp_sum(r);
  TValue sum2 = temp_sum(l - 1);
  TValue res = sum1 - sum2;
  return res;
}