Фенвик vs дерево отрезков vs sparse table — что когда выбирать?
Три структуры для запросов на отрезке: дерево Фенвика, дерево отрезков, sparse table. Часто не понимаю, какую брать. По каким признакам выбирать? Интересует и время, и память, и что какая умеет.
2 ответа
Короткая матрица выбора:
| Структура | Препроц. | Запрос | Обновление | Память | Операции |
|---|---|---|---|---|---|
| Sparse table | O(n log n) | O(1) | нет | O(n log n) | идемпотентные (min/max/gcd) |
| Disjoint sparse table | O(n log n) | O(1) | нет | O(n log n) | любые ассоциативные |
| Дерево Фенвика (BIT) | O(n) | O(log n) | O(log n) | O(n) | обратимые (сумма, xor) |
| Дерево отрезков | O(n) | O(log n) | O(log n) | O(n) (4n) | любые ассоциативные |
| Segment tree + lazy | O(n) | O(log n) | O(log n) на отрезке | O(n) | + обновление на отрезке |
Логика выбора:
- Данные статичны, нужен min/max/gcd, важна скорость → sparse table (O(1) запрос).
- Нужна сумма с точечными обновлениями, операция обратима → Фенвик (короче кода, меньше константа, чем segment tree).
- Операция не обратима (min/max) ИЛИ нужно сложное слияние/восстановление позиции → дерево отрезков.
- Нужны обновления на отрезке → segment tree с lazy (Фенвик это тоже умеет хитростью, но дерево отрезков универсальнее).
Фенвик не умеет min с произвольными обновлениями (только увеличение), потому что у min нет обратной операции.
Дополню про константу и реальную практику. Фенвик — самый компактный и быстрый по константе для суммы, в 2-3 раза меньше кода. На контесте, если задача — «сумма префикса + точечное обновление», берите Фенвик не раздумывая.
Дерево отрезков проигрывает по константе, но выигрывает по гибкости: восстановление ответа, спуск (k-я единица, первый >= x), хранение структур в узле, lazy. Если сомневаетесь и время позволяет — segment tree почти всегда сработает, просто чуть медленнее.
Sparse table берут редко именно из-за O(n log n) памяти: при n = 2·10^6 и int это уже под 170 МБ для LOG≈21, можно влететь в MLE. Для таких n иногда выгоднее segment tree (O(n) памяти) даже ценой O(log n) запроса. Всегда прикидывайте память, а не только время.