Подсчет инверсий в подмассивах

Учитывая массив arr[] , цель состоит в том, чтобы подсчитать количество инверсий во всех подмассивах. Инверсия — это пара индексов i и j , таких что i > j и arr[i] < arr[j] . Подмассив от индекса x до y ( x<= y) состоит из элементов arr[x], arr[x+1], …, arr[y] . Массив arr[] также может содержать повторяющиеся элементы.

Примеры:

Input: arr[] = {3, 6, 1, 6, 5, 3, 9}
Output: 
0 0 2 2 4 7 7
0 0 1 1 3 6 6
0 0 0 0 1 3 3
0 0 0 0 1 3 3
0 0 0 0 0 1 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0
Explanation: 
The element in the i’th row and j’th column of the output denotes the number of inversions from index i to j (inclusive). Consider i = 1 and j = 4 (assuming 0-based indexing), the number of inversions in the subarray {6, 1, 6, 5} is 3. The element pairs are (6, 1), (6, 5) and (6, 5) (from the second 6). 

Input: arr[] = {3, 2, 1}
Output:  
0 1 3
0 0 1
0 0 0
Explanation: 
From index 0 to 1 there is 1 inversion, from index 2 to 3 there is 1 inversion and from index 0 to 2 there are 3 inversions. The i’th row and j’th column of the output is 0 if i >= j.

Наивный подход. Наивный подход заключается в создании всех возможных подмассивов и подсчете количества инверсий в каждом из подмассивов.

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

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

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

First create a 2d array greater[][], where greater[i][j] denotes the number of elements in the range i to j which are greater than arr[i]. Iterate over the array and for each element, find the number of elements to its right which are less than the element. This can be done using a naive approach in O(N^2).  Now to find the number of inversions in a range say x to y, the answer will be greater[x][y] + greater[x+1][y] + … + greater[y-1][y] + greater[y][y].

With the greater[][] table this value can be calculated in O(n) for each sub-array resulting in a complexity of O(n^3).(There are O(n^2) sub-array, and it takes O(n) time to compute the number of inversions in each sub-array). To find this value in O(1) each time build a prefix sum table from the greater[][] table where prefix[i][j] denotes the value of greater[0][j] + greater[1][j] + … + greater[i][j]. This table can also be built in O(N^2) time. Now the answer for each sub-array from x to y (inclusive) would become prefix[y][y] – prefix[x-1][y] if x >= 1 and prefix[y][y] if x = 0.

Следуйте шагу ниже, чтобы решить эту проблему:

• Инициализировать массивы больших[][] для хранения где больше[i][j] обозначает количество элементов в диапазоне от i до j , которые больше, чем arr[i], префикс[][] для хранения суммы префиксов для подмассива и инверсий[][] для хранения количество инверсий.
• Итерация в диапазоне [0, N-1] с использованием переменной i :
  • Выполните итерацию в диапазоне [i+1, N-1] , используя переменную j:
    • Обновить большее[i][j] как большее[i][j-1]
    • Если arr[i] больше, чем arr[j], то Увеличивайте Greater[i][j] на 1.
• Итерация в диапазоне [0, N-1] с использованием переменной i :
  • Обновить префикс[0][j] как больший[0][j]
  • Выполнить итерацию в диапазоне [1, N-1] , используя переменную j и обновить префикс [i][j] как префикс [i-1][j] + больше[i][j].
• Итерация в диапазоне [0, N-1] с использованием переменной i :
  • Итерация в диапазоне [i, N-1] с использованием переменной j:
    • Если i = 0, то обновить инверсии[i][j] как префикс [j][j]
    • В противном случае обновите инверсии[i][j] как префикс[j][j] + префикс[i-1][j].
• После выполнения вышеуказанных шагов выведите массив inversions[][] в качестве ответа.

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

Временная сложность: O(N ² )
Космическая сложность: O(N ² )

Заметки-

• Некоторое пространство можно сэкономить, построив таблицу префиксов[][] поверх таблицы больших[][], но порядок останется прежним.
• Невозможно работать лучше, чем O (N ^ 2), если вы хотите найти точное количество инверсий во всех подмассивах, поскольку количество подмассивов всегда равно O (N ^ 2).