не могу придумать как проталкивать информацию о необходимости обменов на отрезке. точнее придумал как это сделать за O(h):

пусть есть дерево curr_tree - нужный нам отрезок. корень нужно непосредственно обменять с его парой(это будет либо левый, либо правый потомок). Т.е. разделяем curr_tree на left, right, M1, M2 (где M1, M2 деревья, состоящие из 1 вершины - те, которые мы хотим поменять местами). У left и right изменяем информацию о перевороте. Потом склеиваем как left + M2 + M1 + right. но такая реализация TLится.

может можно проталкивать за O(1)?