DevDays
← Усі нотатки

Нотатка · Алгоритми

Дерево Фенвіка: що робить i & -i

У Telegram:

У дереві Фенвіка кожна позиція зберігає суму блоку. Розмір цього блоку можна отримати так:

i & -i

Першого разу цей вираз виглядає як чаклунство. Насправді він просто залишає наймолодший установлений біт числа — крайню праву одиницю в його двійковому записі.

Розберемо число 6:

6 = 00000110

Щоб отримати -6, комп’ютер інвертує біти й додає одиницю:

  00000110
↓ інвертуємо
  11111001
↓ додаємо 1
  11111010

Тепер виконуємо побітове AND:

  00000110
& 11111010
----------
  00000010

Отримали 2.

Отже:

6 & -6 = 2

Саме два елементи входять до блоку, який закінчується на шостій позиції:

[5–6]

Інший приклад — позиція 4:

4 = 00000100
4 & -4 = 4

Тому четверта комірка зберігає блок із чотирьох чисел:

[1–4]

Для позиції 7 результат дорівнює одиниці:

7 = 00000111
7 & -7 = 1

Отже, сьома комірка відповідає лише за себе:

[7]

Тепер можна знайти суму перших семи чисел.

Починаємо з позиції 7. Її блок має розмір 1, тому додаємо tree[7] і переходимо до позиції 6:

7 - 1 = 6

Шоста позиція зберігає блок із двох чисел. Додаємо tree[6] і переходимо до четвертої:

6 - 2 = 4

Четверта зберігає чотири числа:

4 - 4 = 0

Дійшли до нуля — сума готова:

tree[7] + tree[6] + tree[4]

У коді це виглядає так:

def prefix_sum(i):
    result = 0

    while i > 0:
        result += tree[i]
        i -= i & -i

    return result

Під час оновлення рухаємося в інший бік. Якщо змінилася третя позиція, потрібно оновити всі більші блоки, які її містять:

3 → 4 → 8

Для цього розмір блоку не віднімаємо, а додаємо:

def add(i, value):
    while i <= n:
        tree[i] += value
        i += i & -i

Замість проходу по всьому масиву кожна операція відвідує лише кілька комірок. Для мільйона елементів це приблизно двадцять переходів.

Концепція справді проста: зберігаємо суми правильно підібраних блоків і пересуваємося між ними. Але щоб побачити цю простоту за двійковими числами та i & -i, довелося добряче посидіти.

Ще нотатки