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

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

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

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

[править | править код]

Будем обозначать для натурального числа максимальный делитель , являющийся степенью двойки (единицу мы также считаем степенью двойки). Нетрудно убедиться, что F(n)=n−(n & (n−1)), где & — побитовое «И» двух целых чисел. Пусть наш массив имеет элементов: . Выберем , при котором . Тогда для хранения дерева Фенвика понадобится массив из элементов. Будем нумеровать их от 1 до . В ячейке будет храниться сумма в ячейках массива с по .

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

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

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

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

modify (N,X)

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


count (N)

1)   res=0

2)   i=N

3)   Пока

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

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

4)   Ответ = res

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

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

[править | править код]

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

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

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

Для хранения дерева, кроме массива , будем использовать массивы и . В -й ячейке массива будем хранить максимум на отрезке ; в -й ячейке массива  — максимум на отрезке при и на отрезке при .

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

modify (N,X)

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

2)i=N

3)Пока

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

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

4)j=N

5)Пока

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

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

count (L,R)

1)res=0

2)i=L

3)Пока

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

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

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

5)j=R

6)Пока

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

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

7)Ответ = res

Сложность операций = .

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

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

Примечания

[править | править код]
  1. Boris Ryabko. Быстрый последовательный код. // Доклады АН СССР : журнал. — 1989. — Т. 306, № 3. — С. 548—552. Архивировано 17 июля 2019 года.
  2. Boris Ryabko. A fast on-line adaptive code (англ.) // IEEE Trans.on Inform.Theory. — 1992. — Vol. 28, no. 1. — P. 1400—1404. Архивировано 14 июля 2019 года.
  3. Peter M. Fenwick. A new data structure for cumulative frequency tables (англ.) // Software: Practice and Experience : journal. — 1994. — Vol. 24, no. 3. — P. 327—336. — doi:10.1002/spe.4380240306. Архивировано 25 февраля 2021 года.