Изменения

Перейти к: навигация, поиск

Дерево Фенвика

172 байта убрано, 16:02, 29 мая 2015
Нет описания правки
{| style="background-color:#CCC;margin:0.5px"
|style="background-color:#EEE;padding:2px 30px3px 10px"| <tex>i</tex>, десятичная запись|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>1</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>2</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>3</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>4</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>5</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>6</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>7</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>8</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>9</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>10</tex>
|-
|style="background-color:#EEE;padding:2px 30px3px 10px"| <tex>i</tex>, двоичная запись|style="background-color:#FFF;padding:2px 30px"| <tex>0000</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>0001</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>0010</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>0011</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>0100</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>0101</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>0110</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>0111</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>1000</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>1001</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>1010</tex>
|-
|style="background-color:#EEE;padding:2px 30px3px 10px"| <tex>F(i)</tex>, двоичная запись|style="background-color:#FFF;padding:2px 30px"| <tex>0000</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>0000</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>0010</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>0000</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>0100</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>0100</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>0110</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>0000</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>1000</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>1000</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>1010</tex>
|-
|style="background-color:#EEE;padding:2px 30px3px 10px"| <tex>F(i)</tex>, десятичная запись|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>2</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>4</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>4</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>6</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>8</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>8</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>10</tex>
|}
|style="background-color:#FFF;padding:2px 30px"| <tex>\ldots 111 \ldots 1</tex>
|}
 
Несложно заметить, что данная последовательность строго возрастает и в худшем случае будет применена логарифм раз, так как добавляет каждый раз по одной единице в двоичном разложении числа <tex>i</tex>.
В качестве бинарной операции <tex> \circ </tex> рассмотрим операцию сложения. <br/>
Обозначим <tex> \circ_i G_i = \mathrm sum(i) = \sum\limits_{k = 0}^{i} a_k </tex>. Тогда <tex> \mathrm sum(i, j) = \sum\limits_{k = i}^{j} a_k = \circ_j G_j - \circ_G_{i - 1} </tex>.
{{Лемма
'''return''' result
==Преимущества Сравнение дерева Фенвика и недостатки дерева Фенвикаотрезков==
Главными преимуществами данной конструкции являются простота реализации * И дерево Фенвика, и быстрота ответов на запросы за дерево отрезков занимает <tex> O(\log{n}) </tex>. Также дерево Фенвика позволяет быстро изменять значения памяти, но в массиве и занимает столько же памятислучае, сколько сами элементы массива когда <tex>An = a^k + 1</tex>, дерево Фенвика занимает в 2 раза меньше памяти, чем дерево отрезков.* Дерево Фенвика проще в реализации.Недостатком является то* Функция, для которой строится дерево Фенвика, должна быть обратимой, а это значит, что минимум и максимум это дерево считать не все функции, которые могут использоваться в дереве отрезков может (напримерза исключением случаев, минимумкогда некоторыми данными мы можем пожертвовать), применимы к дереву Фенвикав отличие от дерева отрезков.
== См. также ==
* [http://en.wikipedia.org/wiki/Fenwick_tree Wikipedia — Fenwick_tree Fenwick tree]
* [http://e-maxx.ru/algo/fenwick_tree Maximal:: algo:: Дерево Фенвика]
* [http://habrahabr.ru/post/112828 Хабрахабр - Дерево Фенвика]
[[Категория: Дерево Фенвика]]
 
[[Категория: Структуры данных]]
Конспектор
146
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/47019»

Навигация