Дерева Фенвіка (Бінарні індексизовані дерева): Швидні суми

Задача про префіксну суму та проблеми звичайних масивів

Префіксна сума (або накопичена сума) на позиції i – це сума всіх елементів масиву від початку до i. Багато реальних задач полягають у тому, щоб відповідати на багато запитів про префіксні або діапазонні суми, тоді як основні дані постійно змінюються. Звичайний масив має два очевидних стратегії, і кожна з них швидка лише в одному з двох завдань. Стратегія одна: зберігати необроблений масив та перераховувати суму з нуля щоразу, коли хтось запитує її, проходячи по всіх елементах у діапазоні. Оновлення відбуваються миттєво, але запит діапазону великого розміру займає час пропорційний розміру цього діапазону, що неприйнятно, якщо потрібно відповідати на тисячі запитів над мільйонами елементів. Стратегія два: попередньо обчислювати накопичену суму один раз, щоб кожен запит був простим відніманням. Але тепер одне оновлення одного елемента змушує перераховувати всі префіксні суми після нього, що знову займає час пропорційний розміру масиву. Жодна з цих підходів не масштабується, коли оновлення та запити чергуються та відбуваються часто, що є точною ситуацією в живих аналітиках, фінансових скринерах або задачах алгоритмічних конкурсів. Дерево Фенвіка вирішує цю компромісну проблему, зберігаючи не необроблені значення та повну накопичену суму, а оберетний набір часткових сум, кожна з яких відповідає за конкретний, бінарно-вирівняний фрагмент масиву, щоб обидва операції завжди торкалися лише кількох фрагментів.

Прийом з найменшим встановленим бітом

Серцем Fenwick Tree є один бітовий оператор: виділення найменшого встановленого біта індексу, тобто найбільш праву 1-біт у його двійковому представленні. Для індексу i цей значення обчислюється як i AND (від'ємне i), часто записується i & -i в коді, і завжди дорівнює степені двійки. Це одне число точно повідомляє структурі, скільки оригінальних елементів масиву відповідає за сумування кожен слот дерева. Слот 6, чиє бітове представлення становить 110, має найменший встановлений біт 2, тому він зберігає суму блоку з 2 елементами. Слот 8, бітове представлення якого 1000, має найменший встановлений біт 8, тому він зберігає суму повного блоку з 8 елементів. Слот 5, бітове представлення якого 101, має найменший встановлений біт 1, тому він зберігає лише власне значення. Цей шаблон не є випадковим: він безпосередньо випливає з того, як бінарні числа розкладаються на степені двійки, і гарантує, що будь-який префіксний суматор можна відновити за допомогою щонайбільше log n таких блоків, а будь-яке одне оновлення торкається щонайбільше log n таких блоків. Елегантність полягає в тому, що одна проста арифметична операція, яка застосовується повторно, керує обома напрямками структури: віднімання найменшого встановленого біта веде до початку масиву для запитів, а додавання – до кінця для оновлень.»

Як поширюються оновлення

Коли значення за позицією i в оригінальному масиві змінюється, бінарне дерево Фенвіка (Fenwick tree) потребує оновити кожен слот часткової суми, який належить до блоку, що містить позицію i. Початок відбувається з індексу i, застосовується зміна, потім послідовно додається найнижчий встановлений біт для переходу до наступного слоту, який також охоплює позицію i, і застосовується та сама зміна там, і так далі, поки індекс не перевищить кінець масиву. Оскільки кожен стрибок принаймні подвоює розмір блоку, що торкається, ця ланцюг оновлень має довжину пропорційну log n навіть для масивів з мільйонами записів. Наприклад, оновлення позиції 5 в 8-елементному дереві торкається слоту 5 (розмір блоку 1), потім слоту 6 (розмір блоку 2, оскільки 5 + 1 = 6), потім слоту 8 (розмір блоку 8, оскільки 6 + 2 = 8) і припиняється, тому що 8 вже охоплює весь масив. Оновлено три слоти замість потенційних тисяч. Це – половина сили оновлення бінарного дерева Фенвіка: замість того, щоб завчасно підтримувати повний масив проміжних сум, воно торкається лише невеликого набору блоків, які випадково охоплюють змінену позицію, відкладаючи роботу по об'єднанню значень до моменту, коли фактично запитується їх сума.

Як обчислюються запити агрегації

Обчислення префіксного суми до позиції i працює як дзеркальне відображення процесу оновлення. Починаючи з індексу i, алгоритм читає значення, що зберігається в цьому слоті, потім віднімає найменший встановлений біт, щоб перейти до слоту, який охоплює блок безпосередньо перед ним, додає це значення і повторює цей процес, поки індекс не досягне нуля. Кожне віднімання зменшує індекс принаймні вдвічі, тому цей хід також займає час пропорційний log n. Наприклад, префіксна сума до позиції 7 у дереві з 8 елементів читає слот 7 (що охоплює лише позицію 7), потім переходить до слоту 6 (що охоплює позиції 5-6, оскільки 7 мінус 1 дорівнює 6), потім переходить до слоту 4 (що охоплює позиції 1-4, оскільки 6 мінус 2 дорівнює 4) і зупиняється там, оскільки 4 мінус 4 дорівнює 0. Додавання цих трьох збережених значень дає точну суму позицій від 1 до 7 без необхідності торкатися семи оригінальних елементів окремо. Сума діапазону від позиції a до позиції b, включно, тоді просто є префіксна сума до позиції b мінус префіксна сума до позиції a мінус 1, тому як оновлення окремих точок, так і будь-які запити діапазонів агрегації зводяться до невеликої кількості пошуків в масиві та додавання.

Приклад Розрахунку та Практичне Застосування

Розглянемо масив з 8 елементами з значеннями [3, 2, -1, 6, 5, 4, -3, 3]. Побудова дерева Фенвіка передбачає вставлення кожного значення на власному індексі та дозволяє йому поширюватися вгору точно так само, як оновлення. Таким чином, слот 1 містить 3, слот 2 містить 5 (позиції 1 до 2), слот 3 містить -1 (власне значення), слот 4 містить 10 (позиції 1 до 4), слот 5 містить 5, слот 6 містить 9 (позиції 5 до 6), слот 7 містить -3 і слот 8 містить 19 (позиції 1 до 8, загальна сума). Запит префіксного підсумку до позиції 6 проходить слот 6 (9) плюс слот 4 (10), що дає в сумі 19, коректно відображаючи позиції від 1 до 6. Ця структура зустрічається постійно за межами класної кімнати. У змагальному програмуванні це стандартний інструмент для відповіді на багато запитів про суми діапазонів, які чергуються із оновленнями у точці за логарифмічний час. Це також основна сила при підрахунку перестановки елементів в масиві ефективно, класичної підрутини в аналізі, пов'язаній з сортуванням, та для вимірювання того, наскільки «не упорядкований» послідовність. І у статистиці та інженерії даних, дерева Фенвіка використовують для підтримки частотних таблиць і структур статистики порядку, дозволяючи підтримувати динамічний гістограмний графік та швидко відповідати на запитання «скільки значень було спостережено дотепер нижче x», коли надходять нові дані.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Fenwick Trees (Binary Indexed Trees): Fast Running Totals і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.