Дерево Фенвика (двоичное индексированное дерево, , BIT) — структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива. Впервые описано Рябко Б.Я. в 1989 году. Полная версия опубликована им на английском в 1992 г.
Через два года (в 1994 г.) появилась статья П. Фенвика , где была описана та же структура, впоследствии получившая название "дерево Фенвика".
Дерево Фенвика для суммы Будем обозначать для натурального числа максимальный делитель , являющийся степенью двойки (единицу мы также считаем степенью двойки). Нетрудно убедиться, что F(n)=n−(n & (n−1)), где & — побитовое «И» двух целых чисел. Пусть наш массив имеет элементов: . Для хранения дерева Фенвика понадобится массив из элементов: . В ячейке будет храниться сумма в ячейках массива с по .
Дерево Фенвика для суммы поддерживает 2 операции:
1) modify с аргументами и — изменить значение -й ячейки массива на число ( может быть как положительно, так и отрицательно).
2) count с аргументом — найти сумму чисел в ячейках массива с 1-й по -ю.
Обе операции могут быть легко реализованы одним циклом.
modify (N,X) i=N Пока i <= размера b Увеличить b[i] на X Увеличить i на F(i)
count (N) res=0 i=N Пока i > 0 Увеличить res на b[i] Уменьшить i на F(i) Ответ = res
Сложность обеих операций составляет 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
Сложность операций = .
Важное ограничение дерева Фенвика для максимума состоит в том, что с помощью него нельзя уменьшить значение, записанное в ячейке. Если требуется, чтобы структура данных имела такую возможность, следует использовать дерево отрезков для максимума.
Операции могут быть легко модифицированы, чтобы дерево Фенвика находило не только значение максимума, но и ячейку, в которой этот максимум достигается.
Примечания
Ссылки Рябко Б.Я. "Быстрый последовательный код" , Доклады АН СССР, том 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++ на сайте cp-algorithms.com с примерами задач
Категория:Алгоритмы Категория:Деревья (структуры данных)