Sqrt-декомпозиция или дерево отрезков: как выбрать структуру под запросы на отрезке?
Запутался, когда брать корневую декомпозицию, а когда дерево отрезков. Обе отвечают на запросы на отрезке. По асимптотике дерево лучше (log vs sqrt), но иногда советуют корневую. По каким критериям выбирать на реальной задаче?
2 ответа
Краткий критерий: по умолчанию дерево отрезков (быстрее: O(log n) против O(sqrt n)). Корневую бери, когда дерево писать дольше/неудобно под конкретную операцию.
Когда дерево отрезков:
- Стандартная ассоциативная агрегация: сумма, min, max, gcd, xor — всё кладётся в дерево.
- Нужны массовые операции с lazy propagation (прибавить на отрезке, присвоить на отрезке).
- Много запросов (1e5–1e6): множитель log n критичен, sqrt n даст TLE.
Когда корневая декомпозиция:
- Операция плохо ложится в дерево/lazy, но легко агрегируется по блоку. Пример: «сколько чисел в [l,r] больше x» — храни в каждом блоке отсортированную копию и делай бинпоиск внутри блока. В lazy-дереве это сложно, в корневой — естественно: O(sqrt n · log) на запрос.
- Нужны «странные» обновления (перестановки на блоке, пересортировка блока), которые в дереве не выразить.
- Писать надо быстро, а константа O(sqrt n) проходит по TL (запросов немного).
Грубая численная прикидка: при n = 1e5 дерево даёт ~17 операций на запрос, корневая ~316 — разница в ~18 раз. Если запросов q = 1e5, дерево ~2·10^6 операций (мгновенно), корневая ~3·10^7 (ещё ок), а корневая с лог-фактором внутри блока ~2·10^8 (на грани).
Правило: сначала спроси, влезает ли операция в дерево. Влезает — дерево. Не влезает, но агрегируется поблочно — корневая. Совсем нестандартно/оффлайн — смотри в сторону Мо.
Дополню стороной реализации: корневую быстрее и безопаснее написать на контесте — там нет рекурсии, lazy-распространения, легко дебажить (массив блоков виден глазами). Дерево мощнее, но в нём больше мест ошибиться: индексация (0/1-based), полуинтервалы, lazy push down. Прагматичный выбор на олимпиаде: если задача проходит по TL с sqrt и операция нестандартная — пиши корневую и не рискуй. Если TL жёсткий или нужны lazy-операции на отрезке — дерево, но закладывай время на отладку. Ещё вариант между ними — дерево Фенвика (BIT): если хватает сумм/префиксов, оно короче дерева отрезков и быстрее корневой.