Подсчет отдельных элементов из диапазона отсортированной последовательности из заданного частотного массива

Даны два целых числа L и R и массив arr[] , состоящий из N положительных целых чисел ( индексация на основе 1 ), так что частота i ^-го элемента отсортированной последовательности, скажем, A[] , равна arr[i] . Задача состоит в том, чтобы найти количество различных элементов из диапазона [L, R] в последовательности A[] .

Примеры:

Input: arr[] = {3, 6, 7, 1, 8}, L = 3, R = 7
Output: 2
Explanation: From the given frequency array, the sorted array will be {1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, ….}. Now, the number of distinct elements from the range [3, 7] is 2( = {1, 2}).

Input: arr[] = {1, 2, 3, 4}, L = 3, R = 4
Output: 1

Наивный подход: самый простой подход к решению данной проблемы состоит в том, чтобы построить отсортированную последовательность из заданного массива arr[] , используя заданные частоты, а затем пройти построенный массив по диапазону [L, R], чтобы подсчитать количество различных элементов.

Временная сложность: O(N + R – L)
Вспомогательное пространство: O(S), где S — сумма элементов массива .

Эффективный подход. Описанный выше подход можно оптимизировать, используя двоичный поиск и метод суммы префиксов, чтобы найти количество различных элементов в диапазоне [L, R] . Выполните следующие шаги, чтобы решить данную проблему:

• Инициализируйте вспомогательный массив, скажем, prefix[] , в котором хранится сумма префиксов заданных элементов массива.
• Найдите сумму префикса данного массива и сохраните ее в массиве prefix[] .
• Используя бинарный поиск, найдите первый индекс, для которого значение в prefix[] равно как минимум L , скажем, left .
• Используя бинарный поиск, найдите первый индекс, для которого значение в prefix[] равно как минимум R , скажем, right .
• После выполнения вышеуказанных шагов выведите в качестве результата значение (справа – слева + 1) .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)