Дерево Фенвіка (Binary Indexed Tree)

Коротко: Дерево Фенвіка зберігає масив чисел так, що і зміна значення, і префіксні суми виконуються за O(log n).

Докладніше: Це особливо компактна альтернатива дереву відрізків, коли потрібні лише суми (або схожі оборотні операції). Дерево живе в простому масиві, а обчислення індексів використовує наймолодший встановлений біт.

Подробиці

• Ідея: Позиція i зберігає суму відрізка, довжина якого дорівнює найбільшому степеню двійки, що ділить i.
• Запит: Префіксна сума до i: додати значення, потім i -= i & -i, доки i не стане 0.
• Зміна: Змінити значення на d: додати в i, потім i += i & -i, доки i не перевищить розмір.
• Сума на відрізку: сума(r) - сума(l-1).
• Побудова: Можлива за O(n), пам’ять — лише n чисел.
• Обмеження: Не кожна операція оборотна. Мінімум на відрізку тому зазвичай потребує дерева відрізків.

Див. також: O-нотація