23-06-2023
Дерево Фенвика — структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива. Впервые описано Питером Фенвиком в 1994 году. [1] Дерево Фенвика напоминает дерево отрезков, однако проще в реализации.
Содержание |
Будем обозначать для натурального числа максимальный делитель , являющийся степенью двойки (единицу мы также считаем степенью двойки). Нетрудно убедиться, что 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
Сложность операций = .
Заметим, что с помощью дерева Фенвика для максимума нельзя уменьшить значение, записанное в ячейке. Если требуется, чтобы структура данных имела такую возможность, следует использовать дерево отрезков для максимума.
Операции могут быть легко модифицированы, чтобы дерево Фенвика находило не только значение максимума, но и ячейку, в которой этот максимум достигается.
Дерево (структура данных) | |
---|---|
Двоичное дерево поиска · Дерево (теория графов) · Древовидная структура | |
Двоичные деревья | Двоичное дерево · T-дерево |
Самобалансирующиеся двоичные деревья | АА-дерево · АВЛ-дерево · Красно-чёрное дерево · Расширяющееся дерево · Дерево со штрафами · Декартово дерево · Дерево Фибоначчи |
B-деревья | B-дерево · 2-3-дерево · B+ дерево · B*-дерево · UB-дерево · 2-3-4 дерево · (a,b)-дерево · Танцующее дерево |
Префиксные деревья | Суффиксное дерево · Radix tree · Ternary search tree |
Двоичное разбиение пространства | k-мерное дерево · VP-дерево |
Недвоичные деревья | Дерево квадрантов · Октодерево · Sparse Voxel Octree · Экспоненциальное дерево · PQ-дерево |
Разбиение пространства | R-дерево · R+-дерево · R*-дерево · X-дерево · M-дерево · Дерево Фенвика · Дерево отрезков |
Другие деревья | Куча · TTH · Finger tree · Metric tree · Cover tree · BK-tree · Doubly-chained tree · iDistance · Link-cut tree |
Алгоритмы | Поиск в ширину · Поиск в глубину · DSW-алгоритм · Алгоритм связующего дерева |
Дерево Фенвика.