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

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

Дерево Фенвика для суммы

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

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

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

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

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

modify (N,X)

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

count (N)

1)   res=0

2)   i=N

3)   Пока $i > 0$

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

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

4)   Ответ = res

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

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

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

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

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

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

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

modify (N,X)

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

2)i=N

3)Пока $i\le2^k$

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

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

4)j=N

5)Пока $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)Пока $i +F(i)\le R$

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

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

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

5)j=R

6)Пока $j -F(j)\ge L$

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

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

7)Ответ = res

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

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

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

Примечания

1. ↑ Peter M. Fenwick (1994). «A new data structure for cumulative frequency tables». Software: Practice and Experience 24 (3): 327-336. DOI:10.1002/spe.4380240306.

Ссылки

• А. Лахно Дерево Фенвика. Курс «Структуры данных», МЦНМО.
• Реализация дерева Фенвика на C++ на e-maxx.ru
• Реализация дерева Фенвика на Java
• Статья про дерево Фенвика на Хабрахабре

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