146
правок
Изменения
Нет описания правки
Пусть существует некоторая бинарная операция <tex>\circ</tex>. Чтобы получить значение на отрезке <tex>[i, j]</tex>, нужно провести операцию, обратную к <tex>\circ</tex>, над значениями на отрезках <tex>[0, j]</tex> и <tex>[0, i - 1]</tex>.
В качестве бинарной операции <tex> \circ </tex> рассмотрим операцию сложения. Обратная операция для сложения — вычитание.
Обозначим <tex> 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 = G_j - G_{i - 1} </tex>.
==Сравнение дерева Фенвика и дерева отрезков==
* Дерево Фенвика занимает в константное значение раз меньше памяти, чем [[Дерево отрезков. Построение |дерево отрезков]]. Это следует из того, что дерево Фенвика хранит только значение операции для каких-то элементов, а дерево отрезков хранит сами элементы и частичные результаты операции на подотрезках, поэтому оно занимает как минимум в два раза больше памяти.
* Дерево Фенвика проще в реализации.
* Операция на отрезке, для которой строится дерево Фенвика, должна быть обратимой, а это значит, что минимум (как и максимум ) на отрезке это дерево считать не может, в отличие от дерева отрезков. Но если нам требуется найти минимум на префиксе, то дерево Фенвика справится с этой задачей. Такое дерево Фенвика поддерживает операцию уменьшения элементов массива. Пересчёт минимума в дереве происходит быстрее, чем обновление массива минимумов на префиксе.
== См. также ==
* [http://neerc.ifmo.ru/wiki/index[Дерево отрезков.php?title=%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2._%D0%9F%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D0%B5 Построение |Дерево отрезков]]
==Источники информации==
