Дерево Фенвика — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 97 промежуточных версий 16 участников)
Строка 1: Строка 1:
{{Определение
+
== Описание структуры ==
| definition =
+
[[Файл: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>)
+
'''Дерево Фе&#769;нвика''' (англ. ''Binary indexed tree'') — структура данных, требующая <tex> O(n) </tex> памяти и позволяющая эффективно (за <tex> O(\log n) </tex>) выполнять следующие операции:
# изменять значение любого элемента в массиве;
+
* изменять значение любого элемента в массиве,
# выполнять некоторую бинарную операцию <tex> G </tex> на отрезке <tex> [i, j] </tex>.
+
* выполнять некоторую [[Ассоциативная_операция |ассоциативную]], [[Абелева_группа |коммутативную]], [[Группа |обратимую операцию]] <tex> \circ </tex> на отрезке <tex> [i, j] </tex>.
}}
+
 
 
Впервые описано Питером Фенвиком в 1994 году.
 
Впервые описано Питером Фенвиком в 1994 году.
  
Пусть дан массив <tex> A </tex> из <tex> n </tex> элементов: <tex> a_i, i = \overline{0, n} </tex>.<br/>
+
Пусть дан массив <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, i = \overline{0, n} </tex>, где <tex> F(i) </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>T</tex> при изменении элемента <tex>a_k</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>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>j_{0}</tex> и <tex>k_{0}</tex>. Чтобы выполнялось условие <tex>F(j)  \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>j</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> 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: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>\ldots 011 \ldots 1</tex>
 +
|-
 +
|style="background-color:#EEE;padding:2px 30px"| <tex>i_{prev} + 1</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\ldots 100 \ldots 0</tex>
 +
|-
 +
|style="background-color:#EEE;padding:2px 30px"| <tex>i_{next}</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\ldots 111 \ldots 1</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):
 +
    '''while''' i < N
 +
        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> рассмотрим операцию сложения.
 +
 +
Обозначим <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>.
 +
 +
Для нахождения <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>\log_{2}{i} + 1</tex>. Значит, запрос суммы выполняется за <tex>O(\log{n})</tex>.
 +
 +
=== Реализация ===
 +
Приведем код функции <tex> \mathrm {sum(i)} </tex>:
 +
'''int''' sum(i):
 +
    result = 0
 +
    '''while''' i >= 0
 +
        result += t[i]
 +
        i = f(i) - 1
 +
    return result
 +
 +
==Сравнение дерева Фенвика и дерева отрезков==
 +
 +
* Дерево Фенвика занимает в константное значение раз меньше памяти, чем дерево отрезков. Это следует из того, что дерево Фенвика хранит только значение операции для каких-то элементов, а дерево отрезков хранит сами элементы и частичные результаты операции на подотрезках, поэтому оно занимает как минимум в два раза больше памяти.
 +
* Дерево Фенвика проще в реализации.
 +
* Операция на отрезке, для которой строится дерево Фенвика, должна быть обратимой, а это значит, что минимум (как и максимум) на отрезке это дерево считать не может, в отличие от дерева отрезков. Но если нам требуется найти минимум на префиксе, то дерево Фенвика справится с этой задачей. Такое дерево Фенвика поддерживает операцию уменьшения элементов массива. Пересчёт минимума в дереве происходит быстрее, чем обновление массива минимумов на префиксе.
 +
 +
== См. также ==
 +
* [[Дерево отрезков. Построение |Дерево отрезков]]
 +
 +
==Источники информации==
 +
 +
* [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]
 +
* [http://e-maxx.ru/algo/fenwick_tree Maximal:: algo:: Дерево Фенвика]
 +
* [http://habrahabr.ru/post/112828 Хабрахабр — Дерево Фенвика]
 +
  
== Запрос получения суммы на префиксе ==
+
[[Категория: Дискретная математика и алгоритмы]]
В качестве операции <tex> G </tex> рассмотрим операцию сложения. <br/>
 
Обозначим <tex> G_i = sum(i) = \sum\limits_{k = 0}^{i} a_k </tex>. Тогда <tex> sum(i, j) = \sum\limits_{k = i}^{j} a_k = G_j - G_{i - 1} </tex>.
 
  
Приведем код функции <tex> sum(i) </tex> на C++:
+
[[Категория: Дерево Фенвика]]
<code>
 
int sum(int i)
 
{
 
    int result = 0;
 
    while (i >= 0)
 
    {
 
        result += t[i];
 
        i = f(i) - 1;
 
    }
 
    return result;
 
}
 
</code>
 
  
== Полезные ссылки: ==
+
[[Категория: Структуры данных]]
Peter M. Fenwick: [http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=F180153B9C0CD797594314B736E2CCC5?doi=10.1.1.14.8917&rep=rep1&type=pdf A new data structure for cumulative frequency] <br/>
 
Wikipedia: [http://en.wikipedia.org/wiki/Fenwick_tree Fenwick tree] <br/>
 
e-maxx.ru: [http://e-maxx.ru/algo/fenwick_tree Дерево Фенвика]
 

Текущая версия на 19:18, 4 сентября 2022

Описание структуры

По горизонтали — индексы массива [math]T[/math]
([math]T_i[/math] является суммой элементов массива [math]A[/math], индексы которых заштрихованы),
по вертикали — индексы массива [math]A[/math]

Дерево Фе́нвика (англ. Binary indexed tree) — структура данных, требующая [math] O(n) [/math] памяти и позволяющая эффективно (за [math] O(\log n) [/math]) выполнять следующие операции:

Впервые описано Питером Фенвиком в 1994 году.

Пусть дан массив [math] A = [a_0, a_1, ... , a_{n - 1}][/math]. Деревом Фенвика будем называть массив [math] T [/math] из [math] n [/math] элементов: [math] T_i = \sum\limits_{k = F(i)}^{i} a_k[/math], где [math] i = 0 .. n - 1 [/math] и [math] F(i) [/math] — некоторая функция, от выбора которой зависит время работы операций над деревом. Рассмотрим функцию, позволяющую делать операции вставки и изменения элемента за время [math] O(\log n) [/math]. Она задается простой формулой: [math] F(i) = i \And (i + 1) [/math], где [math] \And [/math] — это операция побитового логического [math]AND[/math]. При [math]AND[/math] числа и его значения, увеличенного на единицу, мы получаем это число без последних подряд идущих единиц.

Эту функцию можно вычислять по другой формуле: [math] F(i) = i - 2^{h(i)} + 1, [/math] где [math] h(i) [/math] — количество подряд идущих единиц в конце бинарной записи числа [math] i [/math]. Оба варианта равносильны, так как функция, заданная какой-либо из этих формул, заменяет все подряд идущие единицы в конце числа на нули.

Запрос изменения элемента

Нам надо научиться быстро изменять частичные суммы в зависимости от того, как изменяются элементы. Рассмотрим как изменяется массив [math]T[/math] при изменении элемента [math]a_k[/math].

Лемма:
Для пересчёта дерева Фенвика при изменении величины [math]a_{k}[/math] необходимо изменить элементы дерева [math]T_{i}[/math], для индексов [math]i[/math] которых верно неравенство [math]F(i) \leqslant k \leqslant i[/math] .
Доказательство:
[math]\triangleright[/math]
[math] T_i =\sum\limits_{k = F(i)}^{i} a_k , i = 0 .. n - 1 \Rightarrow[/math] необходимо менять те [math]T_i[/math], для которых [math]a_{k}[/math] попадает в [math]T_i \Rightarrow[/math] необходимые [math] i [/math] удовлетворяют условию [math]F(i) \leqslant k \leqslant i[/math].
[math]\triangleleft[/math]
Лемма:
Все такие [math] i [/math], для которых меняется [math]T_i[/math] при изменении [math]a_k[/math], можно найти по формуле [math]i_{next} = i_{prev} \mid (i_{prev} + 1) [/math], где [math] \mid [/math] — это операция побитового логического [math] OR [/math].
Доказательство:
[math]\triangleright[/math]
Из доказанной выше леммы следует, что первый элемент последовательности само [math] k [/math]. Для него выполняется равенство, так как [math] F(i) \leqslant i [/math]. По формуле [math]i_{next} = i_{prev} \mid (i_{prev} + 1) [/math] мы заменим первый ноль на единицу. Неравенство при этом сохранится, так как [math]F(i)[/math] осталось прежним или уменьшилось, а [math] i [/math] увеличилось. [math] F(i) [/math] не может увеличиться, так как функция [math] F [/math] заменяет последние подряд идущие единицы числа [math] i [/math] на нули, а по формуле [math]i_{next} = i_{prev} \mid (i_{prev} + 1) [/math] у нового значения [math] i [/math] увеличивается количество единиц в конце, что не может привести к увеличению [math] F(i) [/math]. Докажем от противного, что нельзя рассматривать значения [math] i [/math], отличные от тех, которые мы получили по формуле. Рассмотрим две различные последовательности индексов. Первая последовательность получена по формуле, вторая — некоторая последовательность чисел превосходящих [math]k[/math]. Возьмём число [math] j [/math] из второй последовательности, которого нет в первой последовательности. Пусть [math]F(j) \leqslant k [/math]. Уберём у [math]j[/math] все подряд идущие единицы в конце двоичной записи, столько же цифр уберём в конце числа [math]k[/math]. Обозначим их как [math]j_{0}[/math] и [math]k_{0}[/math]. Чтобы выполнялось условие [math]F(j) \leqslant k [/math], должно выполняться неравенство [math]j_{0} \leqslant k_{0}[/math]. Но если [math]j_{0} \lt k_{0}[/math], то и [math]j \leqslant k[/math], что противоречит условию [math]j \gt k[/math]. Значит, [math]j_{0} = k_{0}[/math]. Но тогда [math]j[/math] возможно получить по формуле [math]i_{next} = i_{prev} \mid (i_{prev} + 1) [/math], следовательно, [math]F(j) \gt k [/math]. Получили противоречие: [math]j[/math] можно вычислить по формуле, а это значит, что оно содержится в первой последовательности. Таким образом, нужные элементы можно искать по формуле [math]i_{next} = i_{prev} \mid (i_{prev} + 1) [/math].
[math]\triangleleft[/math]

Заметим, что [math]F(i)[/math] возрастает немонотонно. Поэтому нельзя просто перебирать значения от [math] k [/math], пока не нарушается условие. Например, пусть [math] k = 3 [/math]. При данной стратегии на следующем шаге ([math] i = 4[/math]) нарушится условие и мы прекратим пересчитывать [math] T_i [/math]. Но тогда мы упускаем остальные значения [math]i[/math], например [math] 7 [/math].

[math]i[/math], десятичная запись [math]0[/math] [math]1[/math] [math]2[/math] [math]3[/math] [math]4[/math] [math]5[/math] [math]6[/math] [math]7[/math] [math]8[/math] [math]9[/math] [math]10[/math]
[math]i[/math], двоичная запись [math]0000[/math] [math]0001[/math] [math]0010[/math] [math]0011[/math] [math]0100[/math] [math]0101[/math] [math]0110[/math] [math]0111[/math] [math]1000[/math] [math]1001[/math] [math]1010[/math]
[math]F(i)[/math], двоичная запись [math]0000[/math] [math]0000[/math] [math]0010[/math] [math]0000[/math] [math]0100[/math] [math]0100[/math] [math]0110[/math] [math]0000[/math] [math]1000[/math] [math]1000[/math] [math]1010[/math]
[math]F(i)[/math], десятичная запись [math]0[/math] [math]0[/math] [math]2[/math] [math]0[/math] [math]4[/math] [math]4[/math] [math]6[/math] [math]0[/math] [math]8[/math] [math]8[/math] [math]10[/math]


Все [math]i[/math] мы можем получить следующим образом: [math]i_{next} = i_{prev} \mid (i_{prev} + 1) [/math]. Следующим элементом в последовательности будет элемент, у которого первый с конца ноль превратится в единицу. Можно заметить, что если к исходному элементу прибавить единицу, то необходимый ноль обратится в единицу, но при этом все следующие единицы обнулятся. Чтобы обратно их превратить в единицы, применим операцию [math]OR[/math]. Таким образом все нули в конце превратятся в единицы и мы получим нужный элемент. Для того, чтобы понять, что эта последовательность верна, достаточно посмотреть на таблицу.

[math]i_{prev}[/math] [math]\ldots 011 \ldots 1[/math]
[math]i_{prev} + 1[/math] [math]\ldots 100 \ldots 0[/math]
[math]i_{next}[/math] [math]\ldots 111 \ldots 1[/math]

Несложно заметить, что данная последовательность строго возрастает и в худшем случае будет применена логарифм раз, так как добавляет каждый раз по одной единице в двоичном разложении числа [math]i[/math].

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

function modify(i, d):
   while i < N
       t[i] += d
       i = i | (i + 1)

Часто можно встретить задачу, где требуется заменить значение элемента [math]a_i[/math] на [math]x[/math]. Заметим, что если вычислить разность [math]x[/math] и [math]a_{i}[/math], то можно свести эту задачу к операции прибавления [math]d[/math] к [math]a_i[/math].

function set(i, x):
   d = x - a[i]
   a[i] = x
   modify(i, d)

Построение дерева можно осуществить, исходя из его описания. Но можно быстрее, если использовать функцию [math]\mathrm {modify}[/math] для каждого элемента массива [math]A[/math]. Тогда мы получим время работы [math]O(n \log {n})[/math].

function build():
   for i = 0 to N - 1
       modify(i, a[i])

Запрос получения значения функции на префиксе

Пусть существует некоторая бинарная операция [math]\circ[/math]. Чтобы получить значение на отрезке [math][i, j][/math], нужно провести операцию, обратную к [math]\circ[/math], над значениями на отрезках [math][0, j][/math] и [math][0, i - 1][/math].

В качестве бинарной операции [math] \circ [/math] рассмотрим операцию сложения.

Обозначим [math] G_i = \mathrm {sum(i)} = \sum\limits_{k = 0}^{i} a_k [/math]. Тогда [math] \mathrm {sum(i, j)} = \sum\limits_{k = i}^{j} a_k = G_j - G_{i - 1} [/math].

Для нахождения [math]\mathrm {sum(i)}[/math] будем действовать следующим образом. Берём [math]T_i[/math], которое является суммой элементов с индексами от [math]F(i)[/math] до [math]i[/math]. Теперь к этому значению нужно прибавить [math]\mathrm {sum(F(i) - 1)}[/math]. Аналогично продолжаем складывать, пока не [math]F(i)[/math] не станет равным [math]0[/math].

Покажем, что запрос суммы работает за [math]O(\log{n})[/math]. Рассмотрим двоичную запись числа [math]i[/math]. Функция [math]F(i)[/math] заменила его последние единицы на нули (заметим, что количество нулей в конце станет больше, чем количество единиц в конце до этого). Теперь вычтем единицу из [math]F(i)[/math] (переход к следующему столбику). Количество единиц в конце увеличилось, по сравнению с [math]i[/math], так как мы заменили все нули в конце на единицы. Проводя эти действия дальше, мы придём к тому, что получили [math]0[/math]. В худшем случае мы должны были повторять эти операции [math]l[/math] раз, где [math]l[/math] — количество цифр в двоичной записи числа [math]i[/math], что не превосходит [math]\log_{2}{i} + 1[/math]. Значит, запрос суммы выполняется за [math]O(\log{n})[/math].

Реализация

Приведем код функции [math] \mathrm {sum(i)} [/math]:

int sum(i):
   result = 0
   while i >= 0
       result += t[i]
       i = f(i) - 1
   return result

Сравнение дерева Фенвика и дерева отрезков

  • Дерево Фенвика занимает в константное значение раз меньше памяти, чем дерево отрезков. Это следует из того, что дерево Фенвика хранит только значение операции для каких-то элементов, а дерево отрезков хранит сами элементы и частичные результаты операции на подотрезках, поэтому оно занимает как минимум в два раза больше памяти.
  • Дерево Фенвика проще в реализации.
  • Операция на отрезке, для которой строится дерево Фенвика, должна быть обратимой, а это значит, что минимум (как и максимум) на отрезке это дерево считать не может, в отличие от дерева отрезков. Но если нам требуется найти минимум на префиксе, то дерево Фенвика справится с этой задачей. Такое дерево Фенвика поддерживает операцию уменьшения элементов массива. Пересчёт минимума в дереве происходит быстрее, чем обновление массива минимумов на префиксе.

См. также

Источники информации