Запросы на поиск минимальной абсолютной разницы между соседними элементами массива в заданных диапазонах

Дан массив arr[] , состоящий из N целых чисел, и массив query[] , состоящий из запросов вида {L, R} , задача для каждого запроса состоит в том, чтобы найти минимум абсолютной разницы между соседними элементами в диапазоне [L , Р] .

Примеры:

Input: arr[] = {2, 6, 1, 8, 3, 4}, query[] = {{0, 3}, {1, 5}, {4, 5}}
Output:
4
1
1
Explanation:
Following are the values of queries performed:

1. The minimum absolute difference between  adjacent element over the range [0, 3] is min(|2 – 6|, |6 – 1|, |1 – 8|) = 4.
2. The minimum absolute difference between  adjacent element over the range [1, 5] is min(|6 – 1|, |1 – 8|, |8 – 3|, |3 – 4| ) = 1.
3. The minimum absolute difference between  adjacent element over the range [4, 5] is min(|3 – 4|) = 1.

Therefore, print 4, 1, 1 as the results of the given queries.

Input: arr[] = [10, 20, 1, 1, 5 ], query[] = [0, 1], [1, 4], [2, 3]
Output:
10
0
0

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

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

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

Эффективный подход. Описанный выше подход также можно оптимизировать с помощью разреженной таблицы, которая поддерживает запросы за постоянное время O(1) с дополнительным пространством O(N log N) . Вместо передачи исходного arr[] передайте diff[] , чтобы получить требуемый ответ. Выполните следующие шаги, чтобы решить проблему:

1. Инициализировать поиск глобального массива[][] для разреженного массива.
2. Определите функцию preprocess(arr, N) и выполните следующие операции:
   • Переберите диапазон [0, N), используя переменную i , и установите значение lookup[i][0] как i .
   • Перебрать диапазон [1, N), используя вложенные переменные j и i , и если arr[lookup[i][j-1]] меньше, чем arr[lookup[i + (1 << (j-1))] [j-1] , затем установите lookup[i][j] как lookup[i][j-1] , в противном случае установите lookup[i][j] как lookup[i + (1 << (j – 1)) ][j – 1] .
3. Определите функцию query(int arr[], int L, int M) и выполните следующие операции:
   • Инициализируйте переменную j как (int)log2(R – L + 1) .
   • Если arr[lookup[L][j]] меньше, чем arr[lookup[R – (1 << j) + 1][j]], то вернуть arr[lookup[L][j]], иначе вернуть arr[lookup[R – (1 << j) + 1][j]] .
4. Определите функцию Min_difference(arr, n, q, m) и выполните следующие операции:
   • Вызовите функцию preprocess(arr, n) для предварительной обработки разреженного массива.
   • Пройдите заданный массив запросов Q[] и значение, возвращаемое функцией query(arr, L, R – 1), дает результат для текущего запроса.
5. Инициализируйте массив diff[] размера N и сохраните абсолютные различия arr[i]-arr[i+1] для каждого значения i .
6. Вызовите функцию Min_difference(diff, N-1, q, m), чтобы найти минимальную абсолютную разницу для каждого запроса.

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

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