Дерево ФенвикаДерево Фенвика (двоичное индексированное дерево, англ. 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) 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
Сложность операций = . Заметим, что с помощью дерева Фенвика для максимума нельзя уменьшить значение, записанное в ячейке. Если требуется, чтобы структура данных имела такую возможность, следует использовать дерево отрезков для максимума. Операции могут быть легко модифицированы, чтобы дерево Фенвика находило не только значение максимума, но и ячейку, в которой этот максимум достигается. Примечания
Ссылки
|