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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 6: Строка 6:
 
}}
 
}}
 
Впервые описано Питером Фенвиком в 1994 году.
 
Впервые описано Питером Фенвиком в 1994 году.
 +
 +
Пусть дан массив <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)}^{i} a_k, i = \overline{0, n} </tex>, где <tex> F(i) </tex> - некоторая функция.
  
 
== Дерево Фенвика, запрос изменения элемента ==
 
== Дерево Фенвика, запрос изменения элемента ==
  
 
== Запрос получения суммы на префиксе ==
 
== Запрос получения суммы на префиксе ==
Пусть дан массив из <tex> n </tex> элементов: <tex> a_i, i = \overline{0, n} </tex>. В качестве операции <tex> G </tex> рассмотрим операцию сложения. <br/>
+
В качестве операции <tex> G </tex> рассмотрим операцию сложения. <br/>
 
Обозначим <tex> G_i = sum(i) = \sum\limits_{k = 0}^{i} a_k </tex>. Тогда <tex> sum(i, j) = \sum\limits_{k = i}^{j} a_k = G_j - G_{i - 1} </tex>.
 
Обозначим <tex> G_i = sum(i) = \sum\limits_{k = 0}^{i} a_k </tex>. Тогда <tex> sum(i, j) = \sum\limits_{k = i}^{j} a_k = G_j - G_{i - 1} </tex>.
  

Версия 06:26, 1 мая 2011

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

Впервые описано Питером Фенвиком в 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] 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].

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

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