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

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

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

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

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

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

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

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

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

modify (N,X)

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

count (N)

1)   res=0

2)   i=N

3)   Пока $i>0$$i>0$ 

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

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

4)   Ответ = res

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

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

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

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

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

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

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

modify (N,X)

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

2)i=N

3)Пока $i\le <!--\; \le \; -->2^k$$i\le2^k$ 

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

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

4)j=N

5)Пока $j>0$$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 <!--\; \le \; -->R$$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 <!--\; \ge \; -->L$$j -F(j)\ge L$ 

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

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

7)Ответ = res

Сложность операций = $O(\log <!--\; \; -->(n))$$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
• Статья про дерево Фенвика на Хабрахабре