Изменения

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

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

Эту функцию можно вычислять по другой формуле: <tex> F(i) = i - 2^{h(i) } + 1}, </tex> где <tex> h(i) </tex> - — количество подряд идущих единиц в конце бинарной записи числа <tex> i </tex>.Эта Оба варианта равносильны, так как функция задается простой формулой: <tex> F(i) = i \& (i + 1) </tex>, заданная какой-либо из этих формул, заменяет все подряд идущие единицы в конце числа на нули.

== Запрос получения суммы на префиксе = Реализация ===В качестве бинарной операции Приведем код функции <tex> G \mathrm {sum(i)} </tex> рассмотрим операцию сложения. <br/>:Обозначим <tex> G_i = '''int''' sum(i) = \sum\limits_{k : result = 0}^{ '''while''' i} a_k </tex>. Тогда <tex> sum(i, j) = \sum\limits_{k 0 result += t[i] i}^{j} a_k = G_j - G_{f(i ) - 1} </tex>. return result

{{Утверждение==Сравнение дерева Фенвика и дерева отрезков==|statement='''Лемма* Дерево Фенвика занимает в константное значение раз меньше памяти, чем дерево отрезков. Это следует из того, что дерево Фенвика хранит только значение операции для каких-то элементов, а дерево отрезков хранит сами элементы и частичные результаты операции на подотрезках, поэтому оно занимает как минимум в два раза больше памяти.''' <tex> a_i </tex> входит * Дерево Фенвика проще в сумму реализации.* Операция на отрезке, для <tex> t_k </tex>которой строится дерево Фенвика, должна быть обратимой, а это значит, что минимум (как и максимум) на отрезке это дерево считать не может, в отличие от дерева отрезков. Но если <tex> \exists jнам требуется найти минимум на префиксе, то дерево Фенвика справится с этой задачей. Такое дерево Фенвика поддерживает операцию уменьшения элементов массива. Пересчёт минимума в дереве происходит быстрее, чем обновление массива минимумов на префиксе. == См. также ==* [[Дерево отрезков. Построение |Дерево отрезков]] ==Источники информации== * [http: k //citeseer.ist.psu.edu/viewdoc/download;jsessionid= i | \cdots(F180153B9C0CD797594314B736E2CCC5?doi=10.1 \cdots .1) j </tex> раз.14.8917&rep=rep1&type=pdf Peter M. Fenwick: A new data structure for cumulative frequency]|proof=Для доказательства леммы рассмотрим битовую запись следующих чисел* [http: <tex> k - 2^{h(k) + 1} \leq i \leq k </tex>/en.wikipedia.org/wiki/Fenwick_tree Wikipedia — Fenwick tree]* <tex> k [http://e- 2^{h(k) + 1} \rightarrow \cdots (0 \cdots 0) <maxx.ru/tex> <bralgo/>fenwick_tree Maximal:: algo:: Дерево Фенвика]* <tex> i \rightarrow \cdots (\cdots) <[http:/tex> <br/>* <tex> k \rightarrow \cdots (1 \cdots 1)<habrahabr.ru/tex>}}Приведем код функции <tex> sum(i) <post/tex> на C++:112828 Хабрахабр — Дерево Фенвика] <code> int sum(int i) {[[Категория: Дискретная математика и алгоритмы]] int result = 0; while (i >= 0) { result += t[i[Категория: Дерево Фенвика]]; i = f(i) - 1; } return result; } </code>

== Полезные ссылки: ==Peter M. Fenwick: [http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=F180153B9C0CD797594314B736E2CCC5?doi=10.1.1.14.8917&rep=rep1&type=pdf A new data structure for cumulative frequency] <br/>Wikipedia: [httpКатегория://en.wikipedia.org/wiki/Fenwick_tree Fenwick treeСтруктуры данных] <br/>e-maxx.ru: [http://e-maxx.ru/algo/fenwick_tree Дерево Фенвика]