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

Дерево Фенвика (двоичное индексированное дерево, англ. Fenwick tree, binary indexed tree, BIT) — структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива. Впервые описано Рябко Б.Я. в 1989 году.^[1] Полная версия опубликована им на английском в 1992 г.^[2]

Через два года (в 1994 г.) появилась статья П. Фенвика ^[3], где была описана та же структура, впоследствии получившая название "дерево Фенвика".

Будем обозначать для натурального числа ${\displaystyle n}$ ${\displaystyle F(n)}$ максимальный делитель ${\displaystyle n}$, являющийся степенью двойки (единицу мы также считаем степенью двойки). Нетрудно убедиться, что F(n)=n−(n & (n−1)), где & — побитовое «И» двух целых чисел. Пусть наш массив ${\displaystyle a}$ имеет ${\displaystyle n}$ элементов: ${\displaystyle a[1],a[2],\dots ,a[n]}$. Выберем ${\displaystyle k}$, при котором ${\displaystyle 2^{k}\geq n}$. Тогда для хранения дерева Фенвика понадобится массив ${\displaystyle b}$ из ${\displaystyle 2^{k}}$ элементов. Будем нумеровать их от 1 до ${\displaystyle 2^{k}}$. В ячейке ${\displaystyle b[t]}$ будет храниться сумма в ячейках массива ${\displaystyle a}$ с ${\displaystyle t-F(t)+1}$ по ${\displaystyle t}$.

Дерево Фенвика для суммы поддерживает 2 операции:

1) modify с аргументами ${\displaystyle N}$ и ${\displaystyle X}$ — изменить значение ${\displaystyle N}$-й ячейки массива ${\displaystyle a}$ на число ${\displaystyle X}$ (${\displaystyle X}$ может быть как положительно, так и отрицательно).

2) count с аргументом ${\displaystyle N}$ — найти сумму чисел в ячейках массива ${\displaystyle a}$ с 1-й по ${\displaystyle N}$-ю.

Обе операции могут быть легко реализованы одним циклом.

modify (N,X)

1)	i=N
2)	Пока i≤${\displaystyle 2^{k}}$
2.1)	Увеличиваем b[i] на X
2.2)	Увеличиваем i на F(i)

count (N)

1)   res=0

2)   i=N

3)   Пока ${\displaystyle i>0}$

3.1)   Увеличиваем res на b[i]

3.2)   Уменьшаем i на F(i)

4)   Ответ = res

Сложность обеих операций составляет O(k) = O(log n). Стоит отметить, что с помощью операции count(N) мы, вообще говоря, можем найти сумму на любом отрезке ${\displaystyle [l,r]}$ за ту же сложность, поскольку при ${\displaystyle l}$≠1 она в точности равняется ${\displaystyle count(r)-count(l-1)}$.

Дерево Фенвика для максимума поддерживает следующие операции:

1) modify с аргументами ${\displaystyle N}$ и ${\displaystyle X}$ — если значение в ${\displaystyle N}$-й ячейке массива ${\displaystyle a}$ меньше ${\displaystyle X}$, то записать в неё число ${\displaystyle X}$. В противном случае оставить значение старым.

2) count с аргументами ${\displaystyle L}$ и ${\displaystyle R}$ — найти максимум чисел в ячейках массива ${\displaystyle a}$ с ${\displaystyle L}$-й по ${\displaystyle R}$-ю.

Для хранения дерева, кроме массива ${\displaystyle a}$, будем использовать массивы ${\displaystyle left}$ и ${\displaystyle right}$. В ${\displaystyle t}$-й ячейке массива ${\displaystyle left}$ будем хранить максимум на отрезке ${\displaystyle [t-F(t)+1,t]}$; в ${\displaystyle t}$-й ячейке массива ${\displaystyle right}$ — максимум на отрезке ${\displaystyle [t,t+F(t)-1]}$ при ${\displaystyle t<2^{k}}$ и на отрезке ${\displaystyle [t,t]}$ при ${\displaystyle t=2^{k}}$.

Ниже приведена реализация операций.

modify (N,X)

1)a[N]=max(a[N],X)

2)i=N

3)Пока ${\displaystyle i\leq 2^{k}}$

3.1)left[i]=max(left[i],X)

3.2)Увеличиваем i на F(i)

4)j=N

5)Пока ${\displaystyle j>0}$

5.1)right[j]=max(right[j],X)

5.2)Уменьшаем j на F(j)

count (L,R)

1)res=0

2)i=L

3)Пока ${\displaystyle i+F(i)\leq R}$

3.1)res=max(res,right[i])

3.2)Увеличиваем i на F(i)

4)res=max(res,a[i])

5)j=R

6)Пока ${\displaystyle j-F(j)\geq L}$

6.1)res=max(res,left[j])

6.2)Уменьшаем j на F(j)

7)Ответ = res

Сложность операций = ${\displaystyle O(\log(n))}$.

Заметим, что с помощью дерева Фенвика для максимума нельзя уменьшить значение, записанное в ячейке. Если требуется, чтобы структура данных имела такую возможность, следует использовать дерево отрезков для максимума.

Операции могут быть легко модифицированы, чтобы дерево Фенвика находило не только значение максимума, но и ячейку, в которой этот максимум достигается.

• Рябко Б.Я. "Быстрый последовательный код" , Доклады АН СССР, том 306, номер 3, стр. 548–552; переведено на английский как A fast on-line code, in Soviet Math. Dokl. 39 (1989), no. 3, 533–537.
• B.Ya Ryabko; A fast on-line adaptive code. IEEE Trans.on Inform.Theory,v.28, n 1, Jul 1992 pp. 1400 - 1404. http://boris.ryabko.net/ryabko1992.pdf
• А. Лахно Дерево Фенвика. Курс «Структуры данных», МЦНМО.
• Реализация дерева Фенвика на C++ на e-maxx.ru
• Реализация дерева Фенвика на Java
• Статья про дерево Фенвика на Хабрахабре

Для улучшения этой статьи желательно: Исправить статью согласно стилистическим правилам Википедии. Переработать оформление в соответствии с правилами написания статей. Оформить статью по правилам. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.