Дерево Фенвика — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Запрос изменения элемента)
Строка 16: Строка 16:
  
 
== Запрос изменения элемента ==
 
== Запрос изменения элемента ==
Нам надо научиться быстро изменять частичные суммы в зависимости от того, как изменяются элементы. Рассмотрим как изменять величину a_{k} на величину d. Тогда нам надо изменить элементы дерева T_{j}, для которых верно неравенство F(j) < k < j. Все j мы можем получить следующим образом : j_{next} = j_{prev} | j_{prev+1}.
+
Нам надо научиться быстро изменять частичные суммы в зависимости от того, как изменяются элементы. Рассмотрим как изменять величину <tex>a_{k}</tex> на величину <tex>d</tex>. Тогда нам надо изменить элементы дерева <tex>T_{j}</tex>, для которых верно неравенство <tex>F(j) \le k \le j</tex>. Все <tex>j</tex> мы можем получить следующим образом : <tex>j_{next} = j_{prev} | j_{prev+1} </tex>.
  
 
== Запрос получения суммы на префиксе ==
 
== Запрос получения суммы на префиксе ==

Версия 22:48, 8 мая 2011

Определение:
Дерево Фе́нвика (Binary indexed tree) - структура данных, требующая [math] O(n) [/math] памяти и позволяющая эффективно (за [math] O(\log n) [/math])
  1. изменять значение любого элемента в массиве;
  2. выполнять некоторую ассоциативную, коммутативную, обратимую операцию [math] G [/math] на отрезке [math] [i, j] [/math].
По горизонтали - содержимое массива T,
по вертикали - содержимое массива A

Впервые описано Питером Фенвиком в 1994 году.

Пусть дан массив [math] A [/math] из [math] n [/math] элементов: [math] a_i, i = \overline{0, n} [/math].
Деревом Фенвика будем называть массив [math] T [/math] из [math] n [/math] элементов: [math] T_i = \sum\limits_{k = F(i)}^{i} a_k, i = \overline{0, n} [/math], где [math] F(i) [/math] - некоторая функция. От выбора функции зависит время работы операций над деревом. Рассмотрим функцию, позволяющую делать обе операции за время [math] O(\log n) [/math].

[math] F(i) = i - 2^{h(i) + 1}, [/math] где [math] h(i) [/math] - количество единиц в конце бинарной записи числа [math] i [/math]. Эта функция задается простой формулой: [math] F(i) = i \& (i + 1) [/math].

Запрос изменения элемента

Нам надо научиться быстро изменять частичные суммы в зависимости от того, как изменяются элементы. Рассмотрим как изменять величину [math]a_{k}[/math] на величину [math]d[/math]. Тогда нам надо изменить элементы дерева [math]T_{j}[/math], для которых верно неравенство [math]F(j) \le k \le j[/math]. Все [math]j[/math] мы можем получить следующим образом : [math]j_{next} = j_{prev} | j_{prev+1} [/math].

Запрос получения суммы на префиксе

В качестве бинарной операции [math] G [/math] рассмотрим операцию сложения.
Обозначим [math] G_i = sum(i) = \sum\limits_{k = 0}^{i} a_k [/math]. Тогда [math] sum(i, j) = \sum\limits_{k = i}^{j} a_k = G_j - G_{i - 1} [/math].

Лемма:
[math] a_i [/math] входит в сумму для [math] t_k [/math], если [math] \exists j: k = i | (2^j - 1) [/math].

Для доказательства леммы рассмотрим битовую запись следующих чисел: [math] k - 2^{h(k) + 1} \leq i \leq k [/math]

[math]k - 2^{h(k) + 1}[/math] [math]\cdots (0 \cdots 0)[/math]
[math]i[/math] [math]\cdots (\cdots \cdots)[/math]
[math]k[/math] [math]\cdots (1 \cdots 1)[/math]

Реализация

Приведем код функции [math] sum(i) [/math] на C++:


int sum(int i)
{
   int result = 0;
   while (i >= 0)
   {
       result += t[i];
       i = f(i) - 1;
   }
   return result;
}

Полезные ссылки:

Peter M. Fenwick: A new data structure for cumulative frequency
Wikipedia: Fenwick tree
e-maxx.ru: Дерево Фенвика