Как получить доступ к k-му элементу в c ++ std :: set за логарифмическое время?

Question

У меня есть список чисел, в котором мне нужно поддерживать несколько запросов двух типов: либо я могу удалить элемент, либо мне нужно найти k-й наименьший (k может быть разным в каждом запросе) элемент в оставшемся списке.

Поскольку оба они могут поддерживаться в логарифмическом времени, если я использую самобалансирующееся BST, и поскольку std::set реализовано поверх самобалансирующихся BST, должен существовать API для доступа к элементу kth в логарифмическом времени, используя его. Если такого метода нет:

i) Почему? Мне кажется, что это частый случай использования.

ii) Является ли реализация самобалансирующихся деревьев моей единственной надеждой или я могу заставить ее работать, используя что-то еще?

Answer 1

Вам необходимо использовать структуру данных на основе политик.

To delete you can use : erase(T elementToerase)
To find the kth element : find_by_order(int k) where k is 0 based indexing
                          it returns iterator to kth element.

Обе операции O (logn)

для более подробной информации: https://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structures_design.html

Answer 2

самобалансирующиеся BST, должен быть API для доступа к k-му элементу в логарифмическом времени с его использованием

I) почему [нет]?

Насколько мне известно, не существует алгоритма для нахождения n-го элемента в простом сбалансированном BST в логарифмическом времени.

Возможно, вам поможет знать, что сбалансированный BST можетбыть дополненным для достижения логарифмической операции. Название такого дополненного дерева - "дерево статистики заказов".

ii) Реализация самобалансировки деревьев - моя единственная надежда или я могу заставить ее работать, используя что-то еще?

Это не единственный вариант. Как всегда, вы можете использовать существующую реализацию.