146
правок
Изменения
Нет описания правки
|-
|style="background-color:#EEE;padding:3px 10px"| <tex>i</tex>, двоичная запись
|style="background-color:#FFF;padding:3px 10px"| <tex>0000</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>0001</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>0010</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>0011</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>0100</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>0101</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>0110</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>0111</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>1000</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>1001</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>1010</tex>
|-
|style="background-color:#EEE;padding:3px 10px"| <tex>F(i)</tex>, двоичная запись
|style="background-color:#FFF;padding:3px 10px"| <tex>0000</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>0000</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>0010</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>0000</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>0100</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>0100</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>0110</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>0000</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>1000</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>1000</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>1010</tex>
|-
|style="background-color:#EEE;padding:3px 10px"| <tex>F(i)</tex>, десятичная запись
Несложно заметить, что данная последовательность строго возрастает и в худшем случае будет применена логарифм раз, так как добавляет каждый раз по одной единице в двоичном разложении числа <tex>i</tex>.
Напишем функцию, которая будет изменять элемент прибавлять к элементу <tex>a_i</tex> на число <tex>d</tex>, и при этом меняет соответствующие частичные суммы.
'''function''' modify(i, d):
t[i] += d
i = i | (i + 1)
Часто можно встретить задачу, где требуется заменить значение элемента <tex>a_i</tex> на <tex>t</tex>. Заметим, что если вычислить разность <tex>t</tex> и <tex>a_{i}</tex>, то можно свести эту задачу к операции прибавления <tex>d</tex> к <tex>a_i</tex>.
'''function''' set(i, t):
d = t - a[i];
modify(i, d)
== Запрос получения значения функции на префиксе ==
==Сравнение дерева Фенвика и дерева отрезков==
* И дерево Дерево Фенвиказанимает в константное значение раз меньше памяти, и чем [[Дерево отрезков. Построение |дерево отрезков занимает <tex>O(n)</tex> памяти]]. Это следует из того, но в случаечто дерево Фенвика хранит только значение операции для каких-то элементов, когда <tex> n = 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 Хабрахабр - — Дерево Фенвика]
