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

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

По горизонтали — индексы массива [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]) выполнять следующие операции:

• изменять значение любого элемента в массиве,
• выполнять некоторую ассоциативную, коммутативную, обратимую операцию [math] \circ [/math] на отрезке [math] [i, j] [/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]i_{next}[/math].

int next(i):
   return i = i | (i + 1)

Напишем функцию, которая будет прибавлять к элементу [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 = next(i);

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

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

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

Пусть существует некоторая бинарная операция [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] a_i [/math] входит в сумму для [math] t_k [/math], если [math] \exists j: k = i \mid (2^j - 1) [/math].

Для доказательства леммы рассмотрим битовую запись следующих чисел: [math] k - 2^{h(k)} + 1 \leqslant i \leqslant k [/math]

[math]k - 2^{h(k)} + 1[/math]	[math]\ldots (0 \ldots 0)[/math]
[math]i[/math]	[math]\ldots (\ldots \ldots)[/math]
[math]k[/math]	[math]\ldots (1 \ldots 1)[/math]

Реализация

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

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

Построение дерева

Будем строить дерево Фенвика исходя из его описания. Можно заметить, что [math]T_{i}[/math] можно считать быстрее, чем по формуле [math] T_i = \sum\limits_{k = F(i)}^{i} a_k[/math]. Мы можем представить [math]T_{i}[/math] как сумму нескольких элементов дерева с меньшими индексами и [math]a_i[/math] (например, [math]T_{7} = a_{7} + T_{6} + T_{5} + T_{3}[/math]). Рассмотрим, как получается эта сумма. Элемент [math]a_i[/math] не учитывался в предыдущих суммах, поэтому мы его прибавляем к [math]T_i[/math]. [math]a_{i-1}[/math] содержится только в [math]T_{i-1}[/math], поэтому прибавим [math]T_{i-1}[/math]. Так как [math]T_{i-1}[/math] может состоять из нескольких элементов из [math]A[/math], то мы пропустим все такие [math]T_j[/math], которые содержат элементы из [math]T_{i-1}[/math]. Мы знаем, что [math]T_j[/math] содержит [math]a_j[/math], поэтому можно пропустить все такие [math]T_j[/math], где [math]j[/math] входит в диапазон от [math]F(i - 1)[/math] до [math]i - 2[/math] (индексы элементов [math]T_{i-1}[/math]).

Другими словами, представим каждый элемент массива [math]T[/math] как столбик (см. картинку). К [math]a_i[/math] элементу прибавляем [math]T_{i-1}[/math]. Далее прибавляем такой столбик, верхняя граница которого находится на том же уровне, что нижняя граница предыдущего прибавляемого столбика. Прекращаем складывать, когда нижняя граница нового столбика будет равна [math]F(i)[/math].

function init(i)
   t[i] = a[i]
   j = i - 1
   while j >= F(i)
       t[i] += t[j]
       j = F(j) - 1

Такое построение будет работать за [math]O(n \log{n})[/math].

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

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

См. также

• Дерево отрезков

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

• Peter M. Fenwick: A new data structure for cumulative frequency
• Wikipedia — Fenwick tree
• Maximal:: algo:: Дерево Фенвика
• Хабрахабр — Дерево Фенвика