Предполагая, что у меня есть STL set <int> s и int x, как я могу подсчитать количество элементов в s, которые меньше x?
Я ищу решение O(log n) (или подобное, что лучше, чем O(n));
Я уже знаю о std::distance(s.begin(), s.lower_bound(x)), но я считаю, что O(n), потому что set не является произвольным доступом.
Что вам нужно, это "дерево статистики по заказу". Это, по сути, расширенное дерево (двоичный поиск), которое поддерживает дополнительную операцию rank(x), которая дает вам количество элементов с меньшим или равным ключом как элемент x. Глава 14 в Кормене, Лейсерсоне, Ривесте, Штайн; "Введение в алгоритмы" должно дать вам алгоритмический фон.
Существует также реализация на веб.
Я не думаю, что это возможно. Ваш STL-набор - это древовидная структура, поэтому даже проверка наличия элемента - O (log n). Ваши узлы дерева не сохраняют размеры их дочерних элементов в любом поле (насколько я знаю), поэтому количество операций, необходимых для подсчета узлов, которые имеют некоторое свойство, которое не следует непосредственно из правил, используемых для построения дерева, не может быть меньше чем количество этих узлов. Поскольку вы не знаете заранее, сколько узлов имеют значения, меньшие, чем x, наихудшая производительность - когда все узлы меньше x, что означает O (n) наихудшую сложность. Даже если значение x находилось в дереве, вам нужно выполнить операции O (log n), чтобы найти node, но затем нужно посетить все его левые потомки, чтобы подсчитать их, поэтому сложность зависит от количества совпадающих узлов, O (n) в худшем случае. Возможно, с дополнительными данными в узлах дерева можно было бы сделать лучше.
В качестве комментария к моему комментарию: используя красно-черные двоичные деревья поиска (вместо наборов), если каждый node хранит количество узлов, внедренных в этот node (обновляется каждый раз, когда вы вставляете/удаляете node), вы можете получить статистику "количество узлов больше или меньше X" довольно быстро.