Количество элементов по оси X для заданных диапазонов Q

Дан двумерный массив arr[][] , где каждый элемент массива обозначает точку на оси X и количество элементов в этой точке. Дан массив запросов query[] размера Q, где каждый элемент имеет тип {l, r}. Задача состоит в том, чтобы найти количество элементов в заданном диапазоне для каждого запроса.

Примеры:

Input: arr[][]={ {1, 2}, {3, 2}, {4, 5}, {7, 1}, {10, 4} }, queries[] = { {0, 12}, {4, 6}, {2, 8} }
Output: 14, 5, 8
Explanation:
queries[0]: we’ll take score all elements i.e. 2 + 2 + 5 + 1 + 4 = 14
queries[1]: Only the 3rd element can be considered so the score will be 5.
queries[2]: we’ll take elements from 2nd, 3rd and 4th  position i.e. 2 + 5 + 1 = 8

Input: arr[][]={ {1, 6}, {12, 5}, {3, 4, }, {14, 3}, {5, 2} }, queries[] = { {10, 12}, {1, 5}, {10, 15} }
Output: 5, 12, 8
Explanation:
queries[0] : only 2nd element will be considered so the score will be 5 
queries[1]: we’ll take score of elements from 1st, 3rd and 5th  position i.e.  6 + 4 + 2 = 12
queries[2]: we’ll take score of elements from 2nd and 4th  position i.e. 5 + 3 = 8

Подход:

This problem can be solved using the concepts of Prefix Sum Array, Sorting,andBinary Search.
The idea is to sort the array first and calculate the prefix sum of the array and perform binary search to find elements in array.

Выполните следующие шаги, чтобы реализовать идею:

• Сортировать данные массив arr[] , чтобы мы могли легко выбирать элементы.
• Создайте массив суммы префиксов prefixArr[] , где prefixArr[i] представляет общее количество элементов, присутствующих в позиции от 0 до i-1.
• Создайте две переменные start и end где:
  • Начало представляет позицию, которая больше или равна запросам[i][0] и ближе всего к запросам[i][0] и
  • Конец представляет позицию, которая меньше или равна запросам[i][1] и ближе всего к запросам[i][1].
• Найдите начальный и конечный указатели, используя технику двоичного поиска.
• Ответ будет представлять собой сумму элементов, которые встречаются между позициями start и end , которая равна prefixArr[end+1] – prefixArr[start] .

Ниже приведена реализация описанного выше подхода.

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