Алгоритми та структури даних · Senior · Запитання 8 з 75
Коли варто обрати дерево відрізків замість дерева Фенвіка?
- ✓Правильна відповідь: Для запитів min чи max на діапазоні або для оновлень діапазонів
- 2Коли масив ніколи не змінюється після створення
- 3Коли пам'ять має бути строго меншою за n елементів
Пояснення
Дерева Фенвіка підходять для оборотних операцій, як-от суми. Дерево відрізків зберігає агрегат на кожен відрізок і підтримує будь-яку асоціативну операцію (min, max, gcd), а з лінивим поширенням - і оновлення діапазонів. Воно займає приблизно від 2n до 4n вузлів.