Почему рекурсивный query дерева отрезков посещает только O(log n) узлов?
Понимаю, что запрос к дереву отрезков работает за O(log n), но не вижу строгого аргумента. Рекурсия же может ветвиться в обоих детей. Почему суммарно посещается O(log n) узлов, а не больше?
2 ответа
Ключевое наблюдение: на каждом уровне дерева запрос [l, r] «затрагивает» не более 4 узлов, и реально ветвится не более чем в 2 точках на уровень.
Разберём по типам узлов при обходе. Узел может быть: (а) полностью вне [l, r] — рекурсия обрывается сразу; (б) полностью внутри — возвращаем t[v], в детей не идём; (в) частично пересекает границу. Ветвление в обоих детей происходит только в узлах типа (в), а таких на каждом уровне максимум 2 — те, что содержат левую границу l и правую границу r.
Формально: рассмотрим «левую границу» — узлы, через которые проходит позиция l. На каждом уровне это один узел; от него вправо может отколоться один «полностью внутри» сосед. Аналогично справа от r. Значит на каждом из O(log n) уровней посещается O(1) узлов → суммарно O(log n).
Это та же причина, по которой [l, r] разбивается на O(log n) канонических отрезков дерева — фундаментальное свойство, на котором держится вся скорость структуры.
Полезная иллюстрация — посчитать число «канонических» узлов, покрывающих [l, r]. Если запустить query и собирать узлы, для которых сработала ветка «полностью внутри», их будет не больше 2*log2(n). Эти узлы и есть разбиение отрезка.
Этот же факт объясняет, почему lazy propagation сохраняет O(log n): update на отрезке ставит пометки ровно на эти O(log n) канонических узлов, а push спускает их лениво только вдоль путей к границам. Если бы узлов было больше O(log n), вся асимптотика рассыпалась бы.
Практический вывод для отладки производительности: если ваш query внезапно медленный, скорее всего вы забыли ветку «полностью внутри» (if (l == tl && r == tr) return t[v];) и спускаетесь до листьев — это превращает O(log n) в O(n).