Изменения

== Описание структуры ==[[Файл:Bit.jpg|thumb|300px|По горизонтали — индексы массива <tex>T</tex> <br/> (<tex>T_i</tex> является суммой элементов массива <tex>A</tex>, индексы которых заштрихованы),<br/> по вертикали — индексы массива <tex>A</tex>]]'''Дерево Фе&#769;нвика''' (англ. ''Binary indexed tree'') — структура данных, требующая <tex> O(n) </tex> памяти и позволяющая эффективно (за <tex> O(\log n) </tex>)выполнять следующие операции:

* выполнять некоторую [[Ассоциативная_операция |ассоциативную]], [[Абелева_группа |коммутативную]], [[Группа |обратимую операцию ]] <tex> G \circ </tex> на отрезке <tex> [i, j] </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>. Эту функцию можно записать Оба варианта равносильны, так: <tex> F(i) = i - t(i)как функция, </tex> где <tex> t(i) = 2^{h(i)} заданная какой- 1, </tex> то есть число, состоящее либо из <tex> i </tex> единиц. Это значитэтих формул, что функция заменяет все подряд идущие единицы в конце числа на нули. Эта функция задается простой формулой: <tex> F(i) = i \And (i + 1) </tex>, где <tex> \And </tex> — это операция логического <tex>AND</tex>. При <tex>AND</tex> числа и его значения, увеличенного на единицу, мы получаем это число без последних подряд идущих единиц.

Нам надо научиться быстро изменять частичные суммы в зависимости от того, как изменяются элементы. Рассмотрим как изменять величину изменяется массив <tex>a_{k}T</tex> при изменении элемента <tex>a_k</tex>.

Для изменения пересчёта дерева Фенвика при изменении величины <tex>a_{k}</tex> необходимо изменить элементы дерева <tex>T_{i}</tex>, для индексов <tex>i</tex> которых верно неравенство <tex>F(i) \leqslant k \leqslant i</tex> .

<tex> T_i =\sum\limits_{k = F(i)}^{i} a_k , i = 0 .. n - 1 \Rightarrow</tex> необходимо менять те <tex>iT_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>T_i</tex> при изменении <tex>a_k</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> F(i) </tex> не может увеличиться, что если количество единиц в конце не будет совпадать с так как функция <tex> F </tex> заменяет последние подряд идущие единицы числа <tex> k i </tex>на нули, то формула а по формуле <tex>i_{next} = i_{prev} \mid (i_{prev} + 1) </tex> нарушит неравенствоу нового значения <tex> i </tex> увеличивается количество единиц в конце, что не может привести к увеличению <tex> F(i) </tex>. Докажем от противного, потому что либо само нельзя рассматривать значения <tex> i </tex> будет меньше, чем отличные от тех, которые мы получили по формуле. Рассмотрим две различные последовательности индексов. Первая последовательность получена по формуле, вторая — некоторая последовательность чисел превосходящих <tex>k</tex>. Возьмём число <tex> j </tex> из второй последовательности, которого нет в первой последовательности. Пусть <tex>F(j) \leqslant k</tex>. Уберём у <tex>j</tex> все подряд идущие единицы в конце двоичной записи, либо столько же цифр уберём в конце числа <tex>k</tex>. Обозначим их как <tex>j_{0}</tex> и <tex>k_{0}</tex>. Чтобы выполнялось условие <tex> F(ij) \leqslant k </tex>, должно выполняться неравенство <tex>j_{0} \leqslant k_{0}</tex>. Но если <tex>j_{0} < k_{0}</tex>, то и <tex>j \leqslant k</tex> станет больше, чем что противоречит условию <tex>j > k </tex>. Таким образомЗначит, перебраны будут только нужные элементы<tex>j_{0}= k_{0} Все </tex>. Но тогда <tex>ij</tex> мы можем возможно получить следующим образом : по формуле <tex>i_{next} = i_{prev} \mid (i_{prev} + 1) </tex>, следовательно, <tex>F(j) > k </tex>. Следующим элементом Получили противоречие: <tex>j</tex> можно вычислить по формуле, а это значит, что оно содержится в первой последовательности будет элемент. Таким образом, у которого первый с конца ноль превратится в единицунужные элементы можно искать по формуле <tex>i_{next} = i_{prev} \mid (i_{prev} + 1) </tex>. Можно заметить}} Заметим, что если к исходному элементу прибавить единицу<tex>F(i)</tex> возрастает немонотонно. Поэтому нельзя просто перебирать значения от <tex> k </tex>, то необходимый ноль обратится в единицу, но при этом все следующие единицы обнулятсяпока не нарушается условие. Чтобы обратно их превратить в единицыНапример, применим операцию пусть <tex>ORk = 3 </tex>. Таким образом все нули в конце превратятся в единицы При данной стратегии на следующем шаге (<tex> i = 4</tex>) нарушится условие и мы получим нужный элементпрекратим пересчитывать <tex> T_i </tex>. Для тогоНо тогда мы упускаем остальные значения <tex>i</tex>, чтобы понять, что эта последовательность верна, достаточно посмотреть на таблицунапример <tex> 7 </tex>.

|style="background-color:#EEE;padding:3px 10px"| <tex>i</tex>, десятичная запись|style="background-color:#FFF;padding:3px 10px"| <tex>0</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>1</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>2</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>3</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>4</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>5</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>6</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>7</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>8</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>9</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>10</tex>|-|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>, десятичная запись|style="background-color:#FFF;padding:3px 10px"| <tex>0</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>0</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>2</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>0</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>4</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>4</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>6</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>0</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>8</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>8</tex>|style="background-color:#FFF;padding:3px 10px"| <tex>10</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:#FFF;padding:2px 30px"| <tex>\cdots ldots 100 \cdots ldots 0</tex>

|style="background-color:#FFF;padding:2px 30px"| <tex>\cdots ldots 111 \cdots ldots 1</tex>

Несложно заметить, что данная последовательность строго возрастает и в худшем случае будет применена логарифм раз, так как добавляет каждый раз по одной единице в двоичном разложении числа <tex>i</tex>.Напишем функцию, которая будет изменять элемент прибавлять к элементу <tex>a_i</tex> на число <tex>d</tex>, и при этом меняет соответствующие частичные суммы. Так как наш массив содержит <tex>N</tex> элементов, то мы будем искать <tex>i_{next}</tex> до тех пор, пока оно не превышает значение <tex>N</tex>.

== Запрос получения суммы Часто можно встретить задачу, где требуется заменить значение элемента <tex>a_i</tex> на префиксе ==В качестве бинарной операции <tex> G x</tex> рассмотрим операцию сложения. Заметим, что если вычислить разность <tex>x<br/tex>Обозначим и <tex> G_i = \mathrm sum(i) = \sum\limits_{k = 0}^a_{i} a_k </tex>. Тогда , то можно свести эту задачу к операции прибавления <tex>d</tex> к <tex> \mathrm sum(i, j) = \sum\limits_{k = i}^{j} a_k = G_j - G_{i - 1} a_i</tex>.

'''function''' set(i, x): d = x - a[i] a[i] = x modify(i, d) Построение дерева можно осуществить, исходя из его описания. Но можно быстрее, если использовать функцию <tex>\mathrm {modify}</tex> для каждого элемента массива <tex>A</tex>. Тогда мы получим время работы <tex>O(n \log {Леммаn})</tex>.  '''function''' build(): '''for''' i = 0 '''to''' N - 1 modify(i, a[i]) |statement= = Запрос получения значения функции на префиксе ==Пусть существует некоторая бинарная операция <tex> a_i \circ</tex> входит в сумму для . Чтобы получить значение на отрезке <tex> t_k [i, j]</tex>, если нужно провести операцию, обратную к <tex> \exists 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> \mid mathrm {sum(2i, j)} = \sum\limits_{k = i}^{j } a_k = G_j - G_{i - 1) } </tex>. Для нахождения <tex>\mathrm {sum(i)}</tex> будем действовать следующим образом. Берём <tex>T_i</tex>, которое является суммой элементов с индексами от <tex>F(i)</tex> до <tex>i</tex>. Теперь к этому значению нужно прибавить <tex>\mathrm {sum(F(i) - 1)}</tex>. Аналогично продолжаем складывать, пока не <tex>F(i)</tex> не станет равным <tex>0</tex>. Для доказательства леммы рассмотрим битовую Покажем, что запрос суммы работает за <tex>O(\log{n})</tex>. Рассмотрим двоичную запись следующих чисел: числа <tex>i</tex>. Функция <tex>F(i)</tex> заменила его последние единицы на нули (заметим, что количество нулей в конце станет больше, чем количество единиц в конце до этого). Теперь вычтем единицу из <tex>F(i)</tex> (переход к следующему столбику). Количество единиц в конце увеличилось, по сравнению с <tex>i</tex>, так как мы заменили все нули в конце на единицы. Проводя эти действия дальше, мы придём к тому, что получили <tex>0</tex>. В худшем случае мы должны были повторять эти операции <tex>l</tex> раз, где <tex>l</tex> — количество цифр в двоичной записи числа <tex>i</tex>, что не превосходит <tex> k - \log_{2^}{h(k)i} + 1 </tex>. Значит, запрос суммы выполняется за <tex>O(\leqslant i \leqslant k log{n})</tex>.

 Приведем код функции <tex> \mathrm {sum(i) } </tex>:

result = 0;

result += t[i]; i = f(i) - 1; '''return''' result;

==Преимущества Сравнение дерева Фенвика и недостатки дерева Фенвикаотрезков==

Главными преимуществами данной конструкции являются простота * Дерево Фенвика занимает в константное значение раз меньше памяти, чем дерево отрезков. Это следует из того, что дерево Фенвика хранит только значение операции для каких-то элементов, а дерево отрезков хранит сами элементы и частичные результаты операции на подотрезках, поэтому оно занимает как минимум в два раза больше памяти.* Дерево Фенвика проще в реализации и быстрота ответов .* Операция на запросы за <tex> Oотрезке, для которой строится дерево Фенвика, должна быть обратимой, а это значит, что минимум (1как и максимум) </tex>на отрезке это дерево считать не может, в отличие от дерева отрезков. Также Но если нам требуется найти минимум на префиксе, то дерево Фенвика справится с этой задачей. Такое дерево Фенвика позволяет быстро изменять значения в массиве и находить некоторые функции от поддерживает операцию уменьшения элементов массива.Недостатком является тоПересчёт минимума в дереве происходит быстрее, что при изменении одного элемента исходного чем обновление массива, приходится пересчитывать частичные суммы, а это затратно по времениминимумов на префиксе. == См. также ==* [[Дерево отрезков.Построение |Дерево отрезков]]

* [http://en.wikipedia.org/wiki/Fenwick_tree Wikipedia — Fenwick_tree Fenwick tree]