ACM Контестер

І знову Михайло Медведєв порадував нас новою статтею перекладеною на українську мову

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

У статті розглядається структура даних, яка дозволяє знаходити суму сусідніх елементів масиву, а також модифікувати їх за логарифмічний час. Таку структуру називають суматором, у статті вона реалізована за допомогою дерева Фенвіка.

Перейти до огляду і посилань на статті

Представляємо Вашій увазі наступну статтю від Михайла Медведєва про

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

Дерево Фенвика – это структура данных на массиве длины n, которая позволяет совершать следующие операции:

Позволяет найти значение некоторой заданной функции f на любом отрезке [L; R] за время O(log₂n);
Позволяет изменять значение любого элемента массива за O(log₂n);
Требует O(n) памяти, а именно столько, сколько необходимо для хранения массива из n элементов.

Перейти до огляду і посилань на статті