Изменения

Перейти к: навигация, поиск

Дерево Фенвика

4535 байт добавлено, 20:59, 20 октября 2020
→‎Реализация
== Описание структуры ==
[[Файл: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> \circ </tex> на отрезке <tex> [i, j] </tex>.
[[Файл:Bit.jpg|thumb|300px|По горизонтали - индексы массива <tex>T</tex> <br/> (<tex>T_i</tex> является суммой элементов массива <tex>A</tex>, индексы которых заштрихованы),<br/> по вертикали - индексы массива <tex>A</tex>]]
Впервые описано Питером Фенвиком в 1994 году.
{{Лемма
|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>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> 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>i_j_{next0} = i_</tex> и <tex>k_{prev0} </tex>. Чтобы выполнялось условие <tex>F(j) \mid (i_leqslant k </tex>, должно выполняться неравенство <tex>j_{0} \leqslant k_{0}</tex>. Но если <tex>j_{0} < k_{prev0} + 1) </tex> нарушит неравенство, потому что либо само то и <tex> i j \leqslant k</tex> будет меньше, чем что противоречит условию <tex>j >k</tex>. Значит, либо <tex> Fj_{0} = k_{0}</tex>. Но тогда <tex>j</tex> возможно получить по формуле <tex>i_{next} = i_{prev} \mid (ii_{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> k = 3 </tex> . При данной стратегии на следующем шаге (<tex> i = 4 </tex>), нарушится условие и мы прекратим пересчитывать <tex> T_i </tex>. Но тогда мы упускаем остальные значения <tex>i</tex>, например <tex> 7 </tex>.
{| style="background-color:#CCC;margin:0.5px"
|style="background-color:#EEE;padding:2px 30px3px 10px"| <tex>i</tex>, десятичная запись|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>1</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>2</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>3</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>4</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>5</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>6</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>7</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>8</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>9</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>10</tex>
|-
|style="background-color:#EEE;padding:2px 30px3px 10px"| <tex>i</tex>, двоичная запись|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0000</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0001</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0010</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0011</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0100</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0101</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0110</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0111</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>1000</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>1001</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>1010</tex>
|-
|style="background-color:#EEE;padding:2px 30px3px 10px"| <tex>F(i)</tex>, двоичная запись|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0000</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0000</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0010</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0000</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0100</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0100</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0110</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0000</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>1000</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>1000</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>1010</tex>
|-
|style="background-color:#EEE;padding:2px 30px3px 10px"| <tex>F(i)</tex>, десятичная запись|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>2</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>4</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>4</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>6</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>0</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>8</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>8</tex>|style="background-color:#FFF;padding:2px 30px3px 10px"| <tex>10</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>\ldots 011 \ldots 1</tex>
|-
|}
Несложно заметить, что данная последовательность строго возрастает и в худшем случае будет применена логарифм раз, так как добавляет каждый раз по одной единице в двоичном разложении числа <tex>i</tex>.
Несложно заметить, что данная последовательность строго возрастает и в худшем случае будет применена логарифм раз, так как добавляет каждый раз по одной единице в двоичном разложении числа <tex>i</tex>.Напишем функцию, которая будет изменять элемент прибавлять к элементу <tex>a_i</tex> на число <tex>d</tex>, и при этом меняет соответствующие частичные суммы. Так как наш массив содержит <tex>N</tex> элементов, то мы будем искать <tex>i_{next}</tex> до тех пор, пока оно не превышает значение <tex>N</tex>.
'''function''' modify(i, d):
t[i] += d
i = i | (i + 1)
 
Часто можно встретить задачу, где требуется заменить значение элемента <tex>a_i</tex> на <tex>x</tex>. Заметим, что если вычислить разность <tex>x</tex> и <tex>a_{i}</tex>, то можно свести эту задачу к операции прибавления <tex>d</tex> к <tex>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])
== Запрос получения значения функции на префиксе ==
Пусть существует некоторая бинарная операция <tex>\circ</tex>. Чтобы получить значение на отрезке <tex>[i, j]</tex>, нужно провести операцию, обратную к <tex>\circ</tex>, над значениями на отрезках <tex>[0, j]</tex> и <tex>[0, i - 1]</tex>.
В качестве бинарной операции <tex> \circ </tex> рассмотрим операцию сложения. <br/> Обозначим <tex> \circ_i 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>. Для нахождения <tex>\circ_j - mathrm {sum(i)}</tex> будем действовать следующим образом. Берём <tex>T_i</tex>, которое является суммой элементов с индексами от <tex>F(i)</tex> до <tex>i</tex>. Теперь к этому значению нужно прибавить <tex>\circ_mathrm {sum(F(i ) - 1)} </tex>. Аналогично продолжаем складывать, пока не <tex>F(i)</tex> не станет равным <tex>0</tex>.
Покажем, что запрос суммы работает за <tex>O(\log{{Лемма|statement= n})</tex>. Рассмотрим двоичную запись числа <tex> a_i i</tex> входит в сумму для . Функция <tex> t_k F(i)</tex>заменила его последние единицы на нули (заметим, что количество нулей в конце станет больше, если чем количество единиц в конце до этого). Теперь вычтем единицу из <tex> \exists j: k = F(i \mid )</tex> (2^j - 1переход к следующему столбику) . Количество единиц в конце увеличилось, по сравнению с <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>.
{| 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>\ldots (0 \ldots 0)</tex>
|-
|style="background-color:#EEE;padding:2px 30px"| <tex>i</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\ldots (\ldots \ldots)</tex>
|-
|style="background-color:#EEE;padding:2px 30px"| <tex>k</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\ldots (1 \ldots 1)</tex>
|}
=== Реализация ===
 Приведем код функции <tex> \mathrm {sum(i) } </tex>:
'''int''' sum(i):
result = 0;
'''while''' i >= 0
result += t[i]
i = f(i) - 1
'''return''' result
==Преимущества Сравнение дерева Фенвика и недостатки дерева Фенвикаотрезков==
Главными преимуществами данной конструкции являются простота * Дерево Фенвика занимает в константное значение раз меньше памяти, чем дерево отрезков. Это следует из того, что дерево Фенвика хранит только значение операции для каких-то элементов, а дерево отрезков хранит сами элементы и частичные результаты операции на подотрезках, поэтому оно занимает как минимум в два раза больше памяти.* Дерево Фенвика проще в реализации и быстрота ответов .* Операция на запросы за <tex> Oотрезке, для которой строится дерево Фенвика, должна быть обратимой, а это значит, что минимум (\log{n}как и максимум) </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 Построение |Дерево отрезков]] 
==Источники информации==
* [http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=F180153B9C0CD797594314B736E2CCC5?doi=10.1.1.14.8917&rep=rep1&type=pdf Peter M. Fenwick: A new data structure for cumulative frequency]
* [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 Хабрахабр — Дерево Фенвика]
[[Категория: Дерево Фенвика]]
 
[[Категория: Структуры данных]]
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/46974...75096»

Навигация