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

Материал из Викиконспекты
Перейти к: навигация, поиск
(bugfix)
Строка 9: Строка 9:
  
 
Пусть дан массив <tex> A </tex> из <tex> n </tex> элементов: <tex> a_i, i = \overline{0, n} </tex>.<br/>
 
Пусть дан массив <tex> A </tex> из <tex> n </tex> элементов: <tex> a_i, i = \overline{0, n} </tex>.<br/>
Деревом Фенвика будем называть массив <tex> T </tex> из <tex> n </tex> элементов: <tex> T_i = \sum\limits_{k = F(i) + 1}^{i} a_k, i = \overline{0, n} </tex>, где <tex> F(i) </tex> - некоторая функция.
+
Деревом Фенвика будем называть массив <tex> T </tex> из <tex> n </tex> элементов: <tex> T_i = \sum\limits_{k = F(i)}^{i} a_k, i = \overline{0, n} </tex>, где <tex> F(i) </tex> - некоторая функция.
 
От выбора функции зависит время работы операций над деревом. Рассмотрим функцию, позволяющую делать обе операции за время <tex> O(\log n) </tex>.
 
От выбора функции зависит время работы операций над деревом. Рассмотрим функцию, позволяющую делать обе операции за время <tex> O(\log n) </tex>.
  
Строка 19: Строка 19:
 
|statement=
 
|statement=
 
Нам надо научиться быстро изменять частичные суммы в зависимости от того, как изменяются элементы. Рассмотрим как изменять величину <tex>a_{k}</tex> на величину <tex>d</tex>.
 
Нам надо научиться быстро изменять частичные суммы в зависимости от того, как изменяются элементы. Рассмотрим как изменять величину <tex>a_{k}</tex> на величину <tex>d</tex>.
Необходимо изменить элементы дерева <tex>T_{i}</tex>, для которых верно неравенство <tex>F(i) < k \leq i</tex> .
+
Необходимо изменить элементы дерева <tex>T_{i}</tex>, для которых верно неравенство <tex>F(i) \leq k \leq i</tex> .
 
|proof=
 
|proof=
 
<tex> T_i =\sum\limits_{k = F(i)}^{i} a_k , i = \overline{0, n} \Rightarrow</tex> необходимо менять те <tex>i</tex>, для которых <tex>a_{k}</tex> попадает в <tex>T_i \Rightarrow</tex> необходимые <tex> i </tex> удовлетворяют условию <tex>F(i) < k <= i</tex>.
 
<tex> T_i =\sum\limits_{k = F(i)}^{i} a_k , i = \overline{0, n} \Rightarrow</tex> необходимо менять те <tex>i</tex>, для которых <tex>a_{k}</tex> попадает в <tex>T_i \Rightarrow</tex> необходимые <tex> i </tex> удовлетворяют условию <tex>F(i) < k <= i</tex>.
Строка 26: Строка 26:
 
{{Лемма
 
{{Лемма
 
|statement= Можно перебрать все <tex> i </tex>, попадающие под неравенство по формуле <tex>i_{next} = i_{prev}  |  (i_{prev} + 1) </tex>.
 
|statement= Можно перебрать все <tex> i </tex>, попадающие под неравенство по формуле <tex>i_{next} = i_{prev}  |  (i_{prev} + 1) </tex>.
|proof=Первый элемент последовательности само <tex> k </tex>. Для него выполняется равенство, так как <tex> F(i) < i </tex>. По формуле <tex>i_{next} = i_{prev}  |  (i_{prev} + 1) </tex> мы заменим первый ноль на единицу. Неравенство при этом сохраниться, так как <tex>F(i)</tex> осталось прежним, а <tex> i </tex> увеличилось. Можем заметить, что если количество единиц в конце не будет совпадать с <tex> k </tex>, то формула <tex>i_{next} = i_{prev}  |  (i_{prev} + 1) </tex> нарушит неравенство, потому что либо само <tex> i </tex> будет меньше, чем k, либо <tex> F(i) </tex> станет больше, чем <tex> k </tex>. Таким образом, перебраны будут только нужные элементы}}
+
|proof=Первый элемент последовательности само <tex> k </tex>. Для него выполняется равенство, так как <tex> F(i) < i </tex>. По формуле <tex>i_{next} = i_{prev}  |  (i_{prev} + 1) </tex> мы заменим первый ноль на единицу. Неравенство при этом сохранится, так как <tex>F(i)</tex> осталось прежним, а <tex> i </tex> увеличилось. Можем заметить, что если количество единиц в конце не будет совпадать с <tex> k </tex>, то формула <tex>i_{next} = i_{prev}  |  (i_{prev} + 1) </tex> нарушит неравенство, потому что либо само <tex> i </tex> будет меньше, чем k, либо <tex> F(i) </tex> станет больше, чем <tex> k </tex>. Таким образом, перебраны будут только нужные элементы}}
 
      
 
      
 
Все <tex>i</tex> мы можем получить следующим образом : <tex>i_{next} = i_{prev}  |  (i_{prev} + 1) </tex>, Где под | понимают побитовое ИЛИ. Следующим элементом в последовательности будет элемент, у которого первый с конца ноль превратится в единицу. Можно заметить, что если к исходному элементу прибавить единицу, то необходимый ноль обратится в единицу, но при этом все следующие единицы обнулятся. Чтобы обратно их превратить в единицы, применим операцию побитового ИЛИ. Таким образом все нули в конце превратятся в единицы и мы получим нужный элемент. Для того, чтобы понять, что эта последовательность верна, достаточно посмотреть на таблицу.
 
Все <tex>i</tex> мы можем получить следующим образом : <tex>i_{next} = i_{prev}  |  (i_{prev} + 1) </tex>, Где под | понимают побитовое ИЛИ. Следующим элементом в последовательности будет элемент, у которого первый с конца ноль превратится в единицу. Можно заметить, что если к исходному элементу прибавить единицу, то необходимый ноль обратится в единицу, но при этом все следующие единицы обнулятся. Чтобы обратно их превратить в единицы, применим операцию побитового ИЛИ. Таким образом все нули в конце превратятся в единицы и мы получим нужный элемент. Для того, чтобы понять, что эта последовательность верна, достаточно посмотреть на таблицу.

Версия 15:13, 20 января 2013

Определение:
Дерево Фе́нвика (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_{i}[/math], для которых верно неравенство [math]F(i) \leq k \leq i[/math] .
Доказательство:
[math]\triangleright[/math]
[math] T_i =\sum\limits_{k = F(i)}^{i} a_k , i = \overline{0, n} \Rightarrow[/math] необходимо менять те [math]i[/math], для которых [math]a_{k}[/math] попадает в [math]T_i \Rightarrow[/math] необходимые [math] i [/math] удовлетворяют условию [math]F(i) \lt k \lt = i[/math].
[math]\triangleleft[/math]
Лемма:
Можно перебрать все [math] i [/math], попадающие под неравенство по формуле [math]i_{next} = i_{prev} | (i_{prev} + 1) [/math].
Доказательство:
[math]\triangleright[/math]
Первый элемент последовательности само [math] k [/math]. Для него выполняется равенство, так как [math] F(i) \lt i [/math]. По формуле [math]i_{next} = i_{prev} | (i_{prev} + 1) [/math] мы заменим первый ноль на единицу. Неравенство при этом сохранится, так как [math]F(i)[/math] осталось прежним, а [math] i [/math] увеличилось. Можем заметить, что если количество единиц в конце не будет совпадать с [math] k [/math], то формула [math]i_{next} = i_{prev} | (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} | (i_{prev} + 1) [/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], и при этом меняет соответствующие частичные суммы.

int modify(int i, int d)
{
   while (i < N)
   {
       t[i] += d;
       i = i | (i + 1);
   }
}

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

В качестве бинарной операции [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: Дерево Фенвика