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>a_{k}</tex> необходимо изменить элементы дерева <tex>T_{i}</tex>, для индексов <tex>i</tex> которых верно неравенство <tex>F(i) \leqslant k \leqslant i</tex> .
|proof=
<tex> T_i =\sum\limits_{k = F(i)}^{i} a_k , i = 0 .. n - 1 \Rightarrow</tex> необходимо менять те <tex>T_i</tex>, для которых <tex>a_{k}</tex> попадает в <tex>T_i \Rightarrow</tex> необходимые <tex> i </tex> удовлетворяют условию <tex>F(i) \leqslant k \leqslant 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>F(i)</tex> возрастает немонотонно. {| style="background-color:#CCC;margin:0.5px"|style="background-color:#EEE;padding:2px 30px"| <tex>i</tex>, десятичная запись|style="background-color:#FFF;padding:2px 30px"| <tex>0</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>1</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>2</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>3</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>4</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>5</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>6</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>7</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>8</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>9</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>10</tex> |-|style="background-color:#EEE;padding:2px 30px"| <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 30px"| <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 30px"| <tex>F(i)</tex>, десятичная запись|style="background-color:#FFF;padding:2px 30px"| <tex>0</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>0</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>2</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>0</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>4</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>4</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>6</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>0</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>8</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>8</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>10</tex>|}
Все <tex>i</tex> мы можем получить следующим образом : <tex>i_{next} = i_{prev} \mid (i_{prev} + 1) </tex>. Следующим элементом в последовательности будет элемент, у которого первый с конца ноль превратится в единицу. Можно заметить, что если к исходному элементу прибавить единицу, то необходимый ноль обратится в единицу, но при этом все следующие единицы обнулятся. Чтобы обратно их превратить в единицы, применим операцию <tex>OR</tex>. Таким образом все нули в конце превратятся в единицы и мы получим нужный элемент. Для того, чтобы понять, что эта последовательность верна, достаточно посмотреть на таблицу.
