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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 50 промежуточных версий 10 участников)
Строка 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>.
}}
+
 
[[Файл:Bit.jpg|thumb|300px|По горизонтали - содержимое массива T,<br/> по вертикали - содержимое массива A]]
 
 
Впервые описано Питером Фенвиком в 1994 году.
 
Впервые описано Питером Фенвиком в 1994 году.
  
Пусть дан массив <tex> A </tex> из <tex> n </tex> элементов: <tex> a_i, i = 0 .. n - 1 </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 = 0 .. n - 1 </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> O(\log n) </tex>.
 
  
<tex> F(i) = i - 2^{h(i)} + 1, </tex> где <tex> h(i) </tex> - количество единиц в конце бинарной записи числа <tex> i </tex>.
+
Эту функцию можно вычислять по другой формуле: <tex> F(i) = i - 2^{h(i)} + 1, </tex> где <tex> h(i) </tex> количество подряд идущих единиц в конце бинарной записи числа <tex> i </tex>. Оба варианта равносильны, так как функция, заданная какой-либо из этих формул, заменяет все подряд идущие единицы в конце числа на нули.
Эта функция задается простой формулой: <tex> F(i) = i \And (i + 1) </tex>, где <tex> \And </tex> — это операция побитового логического "И".
 
  
 
== Запрос изменения элемента ==
 
== Запрос изменения элемента ==
 +
Нам надо научиться быстро изменять частичные суммы в зависимости от того, как изменяются элементы. Рассмотрим как изменяется массив <tex>T</tex> при изменении элемента <tex>a_k</tex>.
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Нам надо научиться быстро изменять частичные суммы в зависимости от того, как изменяются элементы. Рассмотрим как изменять величину <tex>a_{k}</tex> на величину <tex>d</tex>.
+
Для пересчёта дерева Фенвика при изменении величины <tex>a_{k}</tex> необходимо изменить элементы дерева <tex>T_{i}</tex>, для индексов <tex>i</tex> которых верно неравенство <tex>F(i) \leqslant k \leqslant i</tex> .
Необходимо изменить элементы дерева <tex>T_{i}</tex>, для которых верно неравенство <tex>F(i) \leqslant k \leqslant i</tex> .
 
 
|proof=
 
|proof=
<tex> T_i =\sum\limits_{k = F(i)}^{i} a_k , i = 0 .. n - 1 \Rightarrow</tex> необходимо менять те <tex>i</tex>, для которых <tex>a_{k}</tex> попадает в <tex>T_i \Rightarrow</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>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> — это операция побитового логического "ИЛИ".
+
|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) < 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> будет меньше, чем k, либо <tex> F(i) </tex> станет больше, чем <tex> k </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>i</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:#CCC;margin:0.5px"
|style="background-color:#EEE;padding:2px 30px"| <tex>\i_{prev}</tex>
+
|style="background-color:#EEE;padding:2px 30px"| <tex>i_{prev}</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\cdots 011 \cdots 1</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:#EEE;padding:2px 30px"| <tex>i_{prev} + 1</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\cdots 100 \cdots 0</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:#EEE;padding:2px 30px"| <tex>i_{next}</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\cdots 111 \cdots 1</tex>
+
|style="background-color:#FFF;padding:2px 30px"| <tex>\ldots 111 \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>.
Напишем функцию, которая будет изменять элемент <tex>a_i</tex> на <tex>d</tex>, и при этом меняет соответствующие частичные суммы.
 
  
  modify(i, d):
+
  '''function''' modify(i, d):
     while i < N
+
     '''while''' i < N
 
         t[i] += d
 
         t[i] += d
 
         i = i | (i + 1)
 
         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>.
В качестве бинарной операции <tex> G </tex> рассмотрим операцию сложения. <br/>
+
 
Обозначим <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>.
+
'''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>.
|statement= <tex> a_i </tex> входит в сумму для <tex> t_k </tex>, если <tex> \exists j: k = i \mid (2^j - 1) </tex>.
 
}}
 
Для доказательства леммы рассмотрим битовую запись следующих чисел: <tex> k - 2^{h(k)} + 1 \leqslant i \leqslant k </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 (0 \cdots 0)</tex>
 
|-
 
|style="background-color:#EEE;padding:2px 30px"| <tex>i</tex>
 
|style="background-color:#FFF;padding:2px 30px"| <tex>\cdots (\cdots \cdots)</tex>
 
|-
 
|style="background-color:#EEE;padding:2px 30px"| <tex>k</tex>
 
|style="background-color:#FFF;padding:2px 30px"| <tex>\cdots (1 \cdots 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> \mathrm 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>
 
  
==Преимущества и недостатки дерева Фенвика==
+
* Дерево Фенвика занимает в константное значение раз меньше памяти, чем дерево отрезков. Это следует из того, что дерево Фенвика хранит только значение операции для каких-то элементов, а дерево отрезков хранит сами элементы и частичные результаты операции на подотрезках, поэтому оно занимает как минимум в два раза больше памяти.
 +
* Дерево Фенвика проще в реализации.
 +
* Операция на отрезке, для которой строится дерево Фенвика, должна быть обратимой, а это значит, что минимум (как и максимум) на отрезке это дерево считать не может, в отличие от дерева отрезков. Но если нам требуется найти минимум на префиксе, то дерево Фенвика справится с этой задачей. Такое дерево Фенвика поддерживает операцию уменьшения элементов массива. Пересчёт минимума в дереве происходит быстрее, чем обновление массива минимумов на префиксе.
  
Главными преимуществами данной конструкции являются простота реализации и быстрота ответов на запросы за <tex> O(1) </tex>. Также дерево Фенвика позволяет быстро изменять значения в массиве и находить некоторые функции от элементов массива.
+
== См. также ==
Недостатком является то, что при изменении одного элемента исходного массива, приходится пересчитывать в среднем <tex> O(n) </tex> частичных сумм, а это затратно по времени.
+
* [[Дерево отрезков. Построение |Дерево отрезков]]
  
 
==Источники информации==
 
==Источники информации==
  
 
* [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://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://en.wikipedia.org/wiki/Fenwick_tree Wikipedia — Fenwick tree]
* [http://e-maxx.ru/algo/fenwick_tree e-maxx.ru — Дерево Фенвика]
+
* [http://e-maxx.ru/algo/fenwick_tree Maximal:: algo:: Дерево Фенвика]
 +
* [http://habrahabr.ru/post/112828 Хабрахабр — Дерево Фенвика]
  
  
Строка 100: Строка 158:
  
 
[[Категория: Дерево Фенвика]]
 
[[Категория: Дерево Фенвика]]
 +
 +
[[Категория: Структуры данных]]

Текущая версия на 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

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

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

См. также

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