Программа Javascript для среднего диапазона в массиве

Дан массив из n целых чисел. Вам дано q запросов. Напишите программу, которая выводит минимальное значение среднего в диапазоне от l до r для каждого запроса в новой строке.

Примеры :

Input : arr[] = {1, 2, 3, 4, 5}
        q = 3
        0 2
        1 3
        0 4
Output : 2
         3
         3
Here for 0 to 2 (1 + 2 + 3) / 3 = 2

Input : arr[] = {6, 7, 8, 10}
        q = 2
        0 3
        1 2
Output : 7
         7

Наивный подход: мы можем запустить цикл для каждого запроса от l до r и найти сумму и количество элементов в диапазоне. После этого мы можем вывести пол среднего значения для каждого запроса.

Выход :

2
3
3

Временная сложность: O(n*q), где q — количество запросов, а n — размер массива. Здесь в приведенном выше коде q равно 3, так как функция findMean используется 3 раза.
Вспомогательное пространство: O(1)

Эффективный подход: мы можем найти сумму чисел, используя числа, используя сумму префиксов. ПрефиксSum[i] обозначает сумму первых i элементов. Таким образом, сумма чисел в диапазоне от l до r будет иметь вид prefixSum[r] — prefixSum[l-1]. Количество элементов в диапазоне от l до r будет равно r – l + 1. Итак, теперь мы можем вывести среднее значение диапазона от l до r за O(1).

Выход:

2
3
3

Временная сложность : O(n+q), где q — количество запросов, а n — размер массива. Здесь в приведенном выше коде q равно 3, так как функция findMean используется 3 раза.
Вспомогательное пространство : O(k), где k=1000005.

Пожалуйста, обратитесь к полной статье о среднем диапазоне в массиве для получения более подробной информации!