Чем итеративное дерево отрезков отличается от рекурсивного на практике — что выбрать?
Есть две реализации дерева отрезков — рекурсивная (build/update/query с v, tl, tr) и итеративная bottom-up на массиве 2n. Когда какую брать на контесте? Правда ли итеративная всегда лучше, или у рекурсивной есть преимущества?
2 ответа
Короткий ответ: итеративная — для простых операций без обновлений на отрезке (точечный update + запрос ассоциативной функции). Рекурсивная — когда нужны lazy propagation, спуск, сложное слияние или восстановление ответа.
Итеративное дерево (2n) плюсы: меньше код, в 1.5-2× меньше константа, нет рекурсии (нет риска переполнить стек), отличная локальность по памяти. Идеально для «точечно меняем, спрашиваем сумму/min на отрезке».
Рекурсивное плюсы: естественно поддерживает lazy propagation (обновление на отрезке), спуск по дереву (k-я единица, первый ≥ x, бинпоиск), хранение и слияние сложных структур в узле (max subarray, max+позиция). Реализовать lazy на чисто итеративном дереве можно, но это заметно сложнее и подвержено ошибкам.
Правило: если задача — lazy или descent, берите рекурсивное не раздумывая. Если просто точечные обновления и запросы — итеративное даст лучшую константу. Обе имеют O(log n) на операцию и O(n) памяти; разница в удобстве и константе, а не в асимптотике.
Ещё нюанс — переполнение стека при рекурсии. При n до 10^6 глубина рекурсии ~20, это безопасно. Но если вы пишете рекурсивный build на питоне или на C++ с большими локальными объектами в кадре, на огромных n можно упереться в лимит стека (особенно на старых судьях с 1-8 МБ стека). Итеративное от этого свободно.
На практике многие competitive-программисты держат оба шаблона наготове: короткий итеративный для 80% задач и рекурсивный с lazy для остального. Не пытайтесь натянуть итеративное дерево на задачу с обновлением на отрезке «чтобы покрасивее» — потеряете время на отладку. Выбирайте инструмент под задачу, а не наоборот.