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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
'''Дерево Фе&#769;нвика''' (англ. ''Binary indexed tree'') — структура данных, требующая <tex> O(n) </tex> памяти и позволяющая эффективно (за <tex> O(\log n) </tex>):
 
'''Дерево Фе&#769;нвика''' (англ. ''Binary indexed tree'') — структура данных, требующая <tex> O(n) </tex> памяти и позволяющая эффективно (за <tex> O(\log n) </tex>):
 
* изменять значение любого элемента в массиве,
 
* изменять значение любого элемента в массиве,
* выполнять некоторую ассоциативную, коммутативную, обратимую операцию <tex> \circ </tex> на отрезке <tex> [i, j] </tex>.
+
* выполнять некоторую [[Ассоциативная_операция |ассоциативную]], [[Абелева_группа |коммутативную]], [[Группа |обратимую операцию]] <tex> \circ </tex> на отрезке <tex> [i, j] </tex>.
  
 
[[Файл:Bit.jpg|thumb|300px|По горизонтали - индексы массива <tex>T</tex> <br/> (<tex>T_i</tex> является суммой элементов массива <tex>A</tex>, индексы которых заштрихованы),<br/> по вертикали - индексы массива <tex>A</tex>]]
 
[[Файл:Bit.jpg|thumb|300px|По горизонтали - индексы массива <tex>T</tex> <br/> (<tex>T_i</tex> является суммой элементов массива <tex>A</tex>, индексы которых заштрихованы),<br/> по вертикали - индексы массива <tex>A</tex>]]

Версия 17:22, 24 мая 2015

Дерево Фе́нвика (англ. Binary indexed tree) — структура данных, требующая [math] O(n) [/math] памяти и позволяющая эффективно (за [math] O(\log n) [/math]):

По горизонтали - индексы массива [math]T[/math]
([math]T_i[/math] является суммой элементов массива [math]A[/math], индексы которых заштрихованы),
по вертикали - индексы массива [math]A[/math]

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

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

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

Нам надо научиться быстро изменять частичные суммы в зависимости от того, как изменяются элементы. Рассмотрим как изменяется массив [math]T[/math] при изменении элемента [math]a_k[/math].

Лемма:
Для изменения величины [math]a_{k}[/math] необходимо изменить элементы дерева [math]T_{i}[/math], для которых верно неравенство [math]F(i) \leqslant k \leqslant i[/math] .
Доказательство:
[math]\triangleright[/math]
[math] T_i =\sum\limits_{k = F(i)}^{i} a_k , i = 0 .. n - 1 \Rightarrow[/math] необходимо менять те [math]i[/math], для которых [math]a_{k}[/math] попадает в [math]T_i \Rightarrow[/math] необходимые [math] i [/math] удовлетворяют условию [math]F(i) \leqslant k \leqslant i[/math].
[math]\triangleleft[/math]
Лемма:
Все такие [math] i [/math] удовлетворяют равенству [math]i_{next} = i_{prev} \mid (i_{prev} + 1) [/math], где [math] \mid [/math] — это операция [math] OR [/math].
Доказательство:
[math]\triangleright[/math]
Первый элемент последовательности само [math] k [/math]. Для него выполняется равенство, так как [math] F(i) \leqslant i [/math]. По формуле [math]i_{next} = i_{prev} \mid (i_{prev} + 1) [/math] мы заменим первый ноль на единицу. Неравенство при этом сохранится, так как [math]F(i)[/math] осталось прежним или уменьшилось, а [math] i [/math] увеличилось. Можем заметить, что если количество единиц в конце не будет совпадать с [math] k [/math], то формула [math]i_{next} = i_{prev} \mid (i_{prev} + 1) [/math] нарушит неравенство, потому что либо само [math] i [/math] будет меньше, чем k, либо [math] F(i) [/math] станет больше, чем [math] k [/math]. Таким образом, перебраны будут только нужные элементы
[math]\triangleleft[/math]

Все [math]i[/math] мы можем получить следующим образом : [math]i_{next} = i_{prev} \mid (i_{prev} + 1) [/math]. Следующим элементом в последовательности будет элемент, у которого первый с конца ноль превратится в единицу. Можно заметить, что если к исходному элементу прибавить единицу, то необходимый ноль обратится в единицу, но при этом все следующие единицы обнулятся. Чтобы обратно их превратить в единицы, применим операцию [math]OR[/math]. Таким образом все нули в конце превратятся в единицы и мы получим нужный элемент. Для того, чтобы понять, что эта последовательность верна, достаточно посмотреть на таблицу.

[math]\i_{prev}[/math] [math]\cdots 011 \cdots 1[/math]
[math]i_{prev} + 1[/math] [math]\cdots 100 \cdots 0[/math]
[math]i_{next}[/math] [math]\cdots 111 \cdots 1[/math]


Несложно заметить, что данная последовательность строго возрастает и в худшем случае будет применена логарифм раз, так как добавляет каждый раз по одной единице в двоичном разложении числа [math]i[/math]. Напишем функцию, которая будет изменять элемент [math]a_i[/math] на [math]d[/math], и при этом меняет соответствующие частичные суммы.

function modify(i, d):
   while i < N
       t[i] += d
       i = i | (i + 1)

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

В качестве бинарной операции [math] G [/math] рассмотрим операцию сложения.
Обозначим [math] G_i = \mathrm sum(i) = \sum\limits_{k = 0}^{i} a_k [/math]. Тогда [math] \mathrm 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 \mid (2^j - 1) [/math].

Для доказательства леммы рассмотрим битовую запись следующих чисел: [math] k - 2^{h(k)} + 1 \leqslant i \leqslant 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] \mathrm sum(i) [/math]:

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

Преимущества и недостатки дерева Фенвика

Главными преимуществами данной конструкции являются простота реализации и быстрота ответов на запросы за [math] O(1) [/math]. Также дерево Фенвика позволяет быстро изменять значения в массиве и находить некоторые функции от элементов массива. Недостатком является то, что при изменении одного элемента исходного массива, приходится пересчитывать частичные суммы, а это затратно по времени.

Источники информации