146
правок
Изменения
Нет описания правки
Пусть дан массив <tex> A = [a_0, a_1, ... , a_{n - 1}]</tex>.
Деревом Фенвика будем называть массив <tex> T </tex> из <tex> n </tex> элементов: <tex> T_i = \sum\limits_{k = F(i)}^{i} a_k</tex>, где <tex> i = 0 .. n - 1 </tex> и <tex> F(i) </tex> — некоторая функция, от выбора которой зависит время работы операций над деревом. Рассмотрим функцию, позволяющую делать операции вставки и изменения элемента за время <tex> O(\log n) </tex>. Она задается простой формулой: <tex> F(i) = 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>. Оба варианта равносильны, так как функция, заданная какой-либо из этих формул, заменяет все подряд идущие единицы в конце числа на нули.
== Запрос изменения элемента ==
{{Лемма
|statement= Все такие <tex> i </tex> удовлетворяют равенству <tex>i_{next} = i_{prev} \mid (i_{prev} + 1) </tex>, где <tex> \mid </tex> — это операция побитового логического <tex> OR </tex>.|proof=Первый элемент последовательности само <tex> k </tex>. Для него выполняется равенство, так как <tex> F(i) \leqslant i </tex>. По формуле <tex>i_{next} = i_{prev} \mid (i_{prev} + 1) </tex> мы заменим первый ноль на единицу. Неравенство при этом сохранится, так как <tex>F(i)</tex> осталось прежним или уменьшилось, а <tex> i </tex> увеличилось. Можем заметить, что если количество единиц в конце не будет совпадать с <tex> k </tex>, то формула <tex>i_{next} = i_{prev} \mid (i_{prev} + 1) </tex> нарушит неравенство, потому что либо само <tex> i </tex> будет меньше, чем <tex>k</tex>, либо <tex> F(i) </tex> станет больше, чем <tex> k </tex>. Таким образом, перебраны будут только нужные элементы}}
Все <tex>i</tex> мы можем получить следующим образом : <tex>i_{next} = i_{prev} \mid (i_{prev} + 1) </tex>. Следующим элементом в последовательности будет элемент, у которого первый с конца ноль превратится в единицу. Можно заметить, что если к исходному элементу прибавить единицу, то необходимый ноль обратится в единицу, но при этом все следующие единицы обнулятся. Чтобы обратно их превратить в единицы, применим операцию <tex>OR</tex>. Таким образом все нули в конце превратятся в единицы и мы получим нужный элемент. Для того, чтобы понять, что эта последовательность верна, достаточно посмотреть на таблицу.
{| style="background-color:#CCC;margin:0.5px"
|style="background-color:#EEE;padding:2px 30px"| <tex>\i_{prev}</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\cdots ldots 011 \cdots ldots 1</tex>
|-
|style="background-color:#EEE;padding:2px 30px"| <tex>i_{prev} + 1</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\cdots ldots 100 \cdots ldots 0</tex>
|-
|style="background-color:#EEE;padding:2px 30px"| <tex>i_{next}</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\cdots ldots 111 \cdots ldots 1</tex>
|}
{| style="background-color:#CCC;margin:0.5px"
|style="background-color:#EEE;padding:2px 30px"| <tex>k - 2^{h(k)} + 1</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\cdots ldots (0 \cdots ldots 0)</tex>
|-
|style="background-color:#EEE;padding:2px 30px"| <tex>i</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\cdots ldots (\cdots ldots \cdotsldots)</tex>
|-
|style="background-color:#EEE;padding:2px 30px"| <tex>k</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\cdots ldots (1 \cdots ldots 1)</tex>
|}
=== Реализация ===
result = 0;
'''while''' i >= 0
result += t[i]; i = f(i) - 1; '''return''' result;
==Преимущества и недостатки дерева Фенвика==
Недостатком является то, что при изменении одного элемента исходного массива, приходится пересчитывать частичные суммы, а это затратно по времени.
== См. также ==
* [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 Дерево отрезков]
==Источники информации==
