Структура данных для больших диапазонов последовательных целых чисел?

Предположим, у вас есть большой диапазон последовательных целых чисел в памяти, каждое из которых принадлежит ровно одной категории. Две операции должны быть O (log n): перемещение диапазона из одной категории в другую и нахождение количества категорий для данного диапазона.

Я почти уверен, что вторая операция решается тривиально при правильной реализации первой операции.

Каждое целое число начинается с категории, поэтому я начал с набора сбалансированных BST. Перемещение поддерева из одного BST в другой (например, перемещение диапазона в другую категорию) во время выполнения эквивалентно слиянию двух BST, что составляет O (n1 * n2) [ 1 ].

Это слишком медленно (в Python и C не подходит), и я не мог придумать, как воспользоваться преимуществами внутренней структуры моих данных для создания эффективной операции слияния BST.

Сейчас я смотрю на AVL, красно-черные и интервальные деревья, двоичные кучи и treap. Сравнивать их свойства невозможно. Какую структуру мне следует использовать?

Редактировать (разъяснение проблемы) : Я могу гибко определять, как хранить эти значения и создавать свои структуры данных. У меня нет гибкости в отношении того, как я получаю свой ввод, который исходит от другого приложения, и выглядит следующим образом: КАТЕГОРИЯ (cat3, I, J) . Мое текущее решение создает дерево с узлом для каждого целого числа в диапазоне.Это слишком медленно для размера моего набора данных, поэтому я буду рад переделать архитектуру, если мне будет предложен лучший метод.

Любой запрос может переместить любой возможный диапазон целых чисел в любую категорию. Другими словами, диапазоны перекрываются в смысле CATEGORY (cat1, 1, 10) , за которым следует CATEGORY (cat3, 5, 15) , но не перекрываются в том смысле, что каждое целое число будет находиться ровно в одной категории в любой момент времени.