, где W — длина отрезка, то есть разность между максимальным R и минимальным L во всех запросах. Потому что каждый запрос выполняется за логарифм, значит создает не более логарифма вершин. Ну а максимум вершин может быть O(W), как в обычном дереве.