Я ищу структуру данных, содержащую произвольное количество (скажем, N) целых чисел, которая поддерживает следующие операции:
1) Insert (k) - вставляет целое число k в массив в O (log N ). Если O (log N) невозможно, то также будет приемлемым полилогарифмическое c. Даже сублинейный будет приемлем, но O (N) не будет.
2) Search (k) - Найдите индекс наименьшей записи в массиве, значение которой больше k в O (log N). Опять же, если строго логарифмическое c невозможно, тогда будет работать и полилогарифмическое c.
3) Суффикс (k) - Увеличивает каждый элемент после индекса k и включает его в сублинейное время (предпочтительно полилогарифмий c или строго логарифмий c время).
Идеи, подобные сбалансированному дереву поиска, не будут работать, потому что, хотя оно поддерживает вставку и поиск в O (журнал N), операция суффикса может потребовать от вас обновления каждой отдельной записи, что потенциально является O (N ).
Я знаю, что такая структура данных существует, потому что я знаю, как реализовать такую структуру данных, но я не знаю, есть ли у этой структуры данных имя, и я не знаю, существует ли существующая реализация . Я ищу существующую реализацию для Python, хотя любой другой язык тоже работает.
Кроме того, приятным бонусом была бы операция удаления, которая также выполняется в строго сублинейное время.