Описанные идеи важны, но их вряд ли можно назвать новыми.
О том, как добавить в балансирующееся двоичное дерево поиска возможность получать индекс по элементу и элемент по индексу, написано, например, во втором издании классической книги Кормена (вышло в 2001 году), в 14-й главе. Более того, реализации set с подобными возможностями уже можно найти в g++.
То, как добавить в коллекцию возможность искать элемент по значению, сделав обратный индекс «значение → его индекс или указатель в коллекции», эксплуатируется в ряде известных задач: «как сделать двоичную кучу с возможностью удаления элемента», «как реализовать LRU-кеш».
Действительно, если мы возьмём балансирующееся дерево поиска (с явными или неявными ключами), добавим в узлы ссылки на родителей, а также будем поддерживать мап «значение → указатель в дереве», то мы сможем за O(logN) добавлять элемент, удалять элемент, искать элемент по индексу (если поддерживаем размеры поддеревьев в вершинах) и определять индекс по значению. Более того, в такой структуре мы можем за логарифмическое время выполнять немутирующие запросы на отрезках (например, сумму всех элементов с ключами в данном диапазоне). Если используются неявные ключи, то мы можем ещё и переставлять местами различные участки коллекции, тоже за логарифмическое время.
Если не ошибаюсь, в 2016 году на Чемпионате Урала по программированию я задал Сергею Владимировичу Копелиовичу, который вёл алгоритмы и структуры данных в Санкт-Петербургском АУ, два вопроса касаемо данной идеи:
1) встречалась ли она в каких-либо известных источниках;
2) насколько она концептуально сложна, стоит ли, например, писать статью.
Ответы были примерно такими:
1) вроде бы нет, статей на явно данную тему не было;
2) идею нельзя назвать сложной, хороший студент должен додуматься до неё за 10-20 минут.
Год назад я давал задачу на реализацию подобной структуры на одной из олимпиад ПФО. После тура некоторые команды выразили своё недовольство задачей — «зачем спрашивать настолько очевидные вещи».
О том, как добавить в балансирующееся двоичное дерево поиска возможность получать индекс по элементу и элемент по индексу, написано, например, во втором издании классической книги Кормена (вышло в 2001 году), в 14-й главе. Более того, реализации set с подобными возможностями уже можно найти в g++.
То, как добавить в коллекцию возможность искать элемент по значению, сделав обратный индекс «значение → его индекс или указатель в коллекции», эксплуатируется в ряде известных задач: «как сделать двоичную кучу с возможностью удаления элемента», «как реализовать LRU-кеш».
Действительно, если мы возьмём балансирующееся дерево поиска (с явными или неявными ключами), добавим в узлы ссылки на родителей, а также будем поддерживать мап «значение → указатель в дереве», то мы сможем за O(logN) добавлять элемент, удалять элемент, искать элемент по индексу (если поддерживаем размеры поддеревьев в вершинах) и определять индекс по значению. Более того, в такой структуре мы можем за логарифмическое время выполнять немутирующие запросы на отрезках (например, сумму всех элементов с ключами в данном диапазоне). Если используются неявные ключи, то мы можем ещё и переставлять местами различные участки коллекции, тоже за логарифмическое время.
Если не ошибаюсь, в 2016 году на Чемпионате Урала по программированию я задал Сергею Владимировичу Копелиовичу, который вёл алгоритмы и структуры данных в Санкт-Петербургском АУ, два вопроса касаемо данной идеи:
1) встречалась ли она в каких-либо известных источниках;
2) насколько она концептуально сложна, стоит ли, например, писать статью.
Ответы были примерно такими:
1) вроде бы нет, статей на явно данную тему не было;
2) идею нельзя назвать сложной, хороший студент должен додуматься до неё за 10-20 минут.
Год назад я давал задачу на реализацию подобной структуры на одной из олимпиад ПФО. После тура некоторые команды выразили своё недовольство задачей — «зачем спрашивать настолько очевидные вещи».