Ваш алгоритм достаточно хорош, но его можно сделать гораздо быстрее.В частности, ваш алгоритм имеет O (1) время предварительной обработки, но затем тратит O (n) время на запрос из-за линейной стоимости времени, необходимого для выполнения шага разделения.
Давайте рассмотрим альтернативный подход.Предположим, что все ваши значения были в отсортированном порядке.В этом случае вы можете очень быстро найти количество элементов в диапазоне, просто выполнив два двоичных поиска - первый двоичный поиск, чтобы найти индекс нижней границы, и второй поиск, чтобы найти верхнюю границу, - и вы можете просто вычестьиндексы.Это займет время O (log n).Если вы можете предварительно обработать входной массив, чтобы отсортировать его по времени O (n + k), то этот подход приведет к экспоненциально более быстрому времени поиска.
Чтобы выполнить эту сортировку, как указывал @minitech, вы можетеиспользовать алгоритм сортировки подсчета, который сортирует по времени O (n + k) для целых чисел от 1 до k.Следовательно, использование сортировки подсчета и двоичного поиска вместе дает время установки O (n + k) и время запроса O (log n).
Если вы хотите обменять память на эффективность, вы можете ускоритьэто еще дальше.Предположим, что k - достаточно малое число (скажем, не более 100).Тогда, если вы в порядке, используя O (k) пробел, вы можете ответить на эти запросы за O (1) раз.Идея заключается в следующем: создать таблицу из k элементов, которая представляет для каждого элемента k, сколько элементов исходного массива меньше k.Если у вас есть этот массив, вы можете найти общее количество элементов в некотором поддиапазоне, посмотрев, сколько элементов меньше b и сколько элементов меньше a (каждый за O (1) время), а затем вычесть их.
Конечно, чтобы сделать это, вы должны построить эту таблицу за время O (n + k).Это можно сделать следующим образом.Сначала создайте массив из k элементов, затем выполните итерацию по исходному массиву из n элементов и для каждого элемента увеличьте место в таблице, соответствующее этому числу.Когда вы закончите (за время O (n + k)), вы заполните эту таблицу числом раз, которое каждое из значений в диапазоне 1 - k существует в исходном массиве (это, кстати,как работает сортировка)Затем создайте вторую таблицу из k элементов, в которой будет храниться накопленная частота.Затем выполните итерацию по гистограмме, которую вы построили на первом шаге, и заполните таблицу кумулятивных частот суммарным общим количеством элементов, встречающихся на протяжении всей гистограммы.Этот последний шаг занимает время O (k) для общей суммы времени O (n + k) для настройки.Теперь вы можете отвечать на запросы вовремя O (1).
Надеюсь, это поможет!