Алгоритми та структури даних · Senior · Запитання 7 з 75
Яку задачу розв'язує дерево Фенвіка (binary indexed tree)?
- 1Сортування масиву на місці за лінійний час
- 2Найкоротші шляхи у зваженому дереві з коренем
- ✓Правильна відповідь: Префіксні суми з оновленнями, обидва за O(log n)
Пояснення
Звичайні префіксні суми дають запит за O(1), але оновлення за O(n). Дерево Фенвіка врівноважує обидва на O(log n), використовуючи наймолодший встановлений біт індексу (i & -i) для переходів між діапазонами.