Количество инверсий в массиве с использованием BIT

Счетчик инверсии для массива указывает, насколько далек (или близок) массив от сортировки. Если массив уже отсортирован, то счетчик инверсии равен 0. Если массив отсортирован в обратном порядке, то счетчик инверсии является максимальным.
Два элемента a[i] и a[j] образуют инверсию, если a[i] > a[j] и i < j. Для простоты можно считать, что все элементы уникальны.
Пример:

Input: arr[] = {8, 4, 2, 1}
Output: 6
Explanation: Given array has six inversions: (8,4), (4,2), (8,2), (8,1), (4,1), (2,1).     

Input: arr[] = {3, 1, 2}
Output: 2
Explanation: Given array has two inversions: (3,1), (3,2).

Мы настоятельно рекомендуем вам щелкнуть здесь и попрактиковаться, прежде чем переходить к решению.

Мы уже обсуждали следующие методы для решения счетчика инверсии:

1. Наивная и модифицированная сортировка слиянием
2. Использование дерева AVL

Мы рекомендуем вам обратиться к двоичному индексированному дереву (BIT) перед дальнейшим чтением этого поста.
Решение с использованием BIT размера Θ(maxElement):

• Подход: пройдите через массив и для каждого индекса найдите количество меньших элементов в правой части массива. Это можно сделать с помощью БИТ. Суммируйте количество всех индексов в массиве и выведите сумму.
• Предыстория БИТ:
  1. BIT в основном поддерживает две операции для массива arr[] размера n:
     1. Сумма элементов до arr[i] за время O(log n).
     2. Обновите элемент массива за время O(log n).
  2. BIT реализован с использованием массива и работает в виде деревьев. Обратите внимание, что есть два способа взглянуть на BIT как на дерево.
     1. Операция суммы, где родителем индекса x является «x – (x & -x)».
     2. Операция обновления, в которой родителем индекса x является «x + (x & -x)».
• Алгоритм:
  1. Создайте BIT, чтобы найти количество меньших элементов в BIT для заданного числа, а также переменную result = 0 .
  2. Пройдите массив от конца к началу.
  3. Для каждого индекса проверьте, сколько чисел меньше текущего элемента присутствует в BIT, и добавьте его к результату.
  4. Чтобы получить количество меньших элементов, используется getSum() из BIT.
  5. В его основной идее BIT представляется как массив размером, равным максимальному элементу плюс один. Так что элементы можно использовать в качестве индекса.
  6. После этого мы добавляем текущий элемент в BIT[], выполняя операцию обновления, которая обновляет счетчик текущего элемента с 0 до 1 и, следовательно, обновляет предков текущего элемента в BIT (подробности см. в разделе update() в BIT) .

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

Временная сложность: функция обновления и функция getSum выполняются за O (log (максимальный элемент)). Функция getSum должна выполняться для каждого элемента массива. Таким образом, общая временная сложность: O (nlog (максимальный элемент)).
Вспомогательное пространство: O(maxElement), пространство, необходимое для BIT, представляет собой массив размером с наибольший элемент.

Лучшее решение с использованием BIT размера Θ(n):
Подход: пройдите через массив и для каждого индекса найдите количество меньших элементов в правой части массива. Это можно сделать с помощью БИТ. Суммируйте количество всех индексов в массиве и выведите сумму. Подход остается прежним, но проблема с предыдущим подходом заключается в том, что он не работает для отрицательных чисел, поскольку индекс не может быть отрицательным. Идея состоит в том, чтобы преобразовать данный массив в массив со значениями от 1 до n, а относительный порядок меньших и больших элементов останется прежним.
Пример :

 
arr[] = {7, -90, 100, 1}
It gets  converted to,
arr[] = {3, 1, 4 ,2 }
as -90 < 1 < 7 < 100.

Explanation: Make a BIT array of a number of
elements instead of a maximum element. Changing
element will not have any change in the answer
as the greater elements remain greater and at the
same position. 

Алгоритм:

1. Создайте BIT, чтобы найти количество меньших элементов в BIT для заданного числа, а также переменную result = 0 .
2. Предыдущее решение не работает для массивов, содержащих отрицательные элементы. Итак, преобразуйте массив в массив, содержащий относительную нумерацию элементов, т.е. сделайте копию исходного массива, а затем отсортируйте копию массива и замените элементы в исходном массиве индексами тех же элементов в отсортированном массиве.
   Например, если массив {-3, 2, 0}, то массив преобразуется в {1, 3, 2}.
3. Пройдите массив от конца к началу.
4. Для каждого индекса проверьте, сколько чисел меньше текущего элемента присутствует в BIT, и добавьте его к результату.

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

Временная сложность: функция обновления и функция getSum выполняются за O (log (n)). Функция getSum должна выполняться для каждого элемента массива. Таким образом, общая временная сложность составляет O (nlog (n)).
Вспомогательное пространство: O(n).
Пространство, необходимое для BIT, представляет собой массив размера n.

Эта статья предоставлена Абхираджем Смитом. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсуждаемой выше.