Боюсь, что тогда всё что можно сделать — то же самое, но теперь хранить декартовы и мёржить их каждый раз, обновив всё поддерево (увеличив в нём отрезок и пересортировав его). С ходу не скажу, насколько плохой становится асимптотика.

UPD: ясно, в чём пробема. Мы не можем мёржить, т.к. ключи левого поддерева не всегда меньше всех ключей правого. Будем вынуждены мёржить добавляя элементы по одному.