Таблица инверсий

<wikitex> Пусть $ P = (p_1,p_2,\dots,p_n)$ является перестановкой чисел $ 1, 2,\dots, n$.

Определение:

Инверсией в перестановке $P$ называется всякая пара индексов $i, j$ такая, что $1\leqslant i<j\leqslant n$ и $P[i]>P[j]$.

Определение:

Таблицей инверсий перестановки $ P $ называют такую последовательность $ T = (t_1,t_2,\dots,t_n)$, в которой $t_i$ равно числу элементов перестановки $ P $, стоящих в $ P $ левее числа $i$ и больших $i$.

Алгоритм построения

Таблицу инверсий тривиально построить по определению. Для каждого элемента перестановки считаем количество элементов, больших данного и стоящих в перестановке левее него. Алгоритм построения в псевдокоде выглядит так:

$T[1..n] = 0$ 
$For$ $i = 1..n$
  $For$ $j = 1..(i - 1)$
    $if$ $P[j] > P[i]$
      $T[P[i]] = T[P[i]] + 1$

Сложность данного алгоритма — $O(n^2)$. Уменьшить время работы можно используя дерево отрезков.

Отсортируем элементы перестановки, сохраняя индексы. Массив $M$ будет содержать номер позиции каждого элемента в исходной перестановке. Также заведём массив $S$ длиной $n$, инициализированный нулями. После обработки $i$-го элемента будем вносить значение 1 в ячейку $S[M[i]]$. Обработку начинаем с последнего элемента и двигаемся к началу. Пусть, функция $Sum(i)$ возвращает значение суммы элементов массива $S$ от 1 до $i$ включительно. Тогда $i$-й элемент таблицы инверсий находится так:

$T[i] = Sum(M[i])$ 

Функция Sum реализуется с помощью дерева отрезков. Каждое изменение массива и обращение к функции $Sum$ влечёт за собой $log_2 n$ операций. Таким образом получаем сложность алгоритма $O(n*log_2 n)$

Алгоритм восстановления

Для восстановления таблицы перестановки из таблицы инверсий(не умаляя общности длина таблицы равна n) создаем таблицу, которую будем расширять, по мере добавления в неё чисел, добавляем в эту таблицу число i (где i от n до 1) на позицию k+1, где k - число в таблице инверсий на i-том месте.

Получение таблицы перестановки из таблицы инверсии [2 3 6 4 0 2 2 1 0] - т. инверсии [9] [9 8] [9 8 7] [9 8 6 7] [5 9 8 6 7] [5 9 8 6 4 7] [5 9 8 6 4 7 3] [5 9 8 2 6 4 7 3] [5 9 1 8 2 6 4 7 3] - т. перестановки

</wikitex>

Получение таблицы инверсии из таблицы перестановки [5 9 1 8 2 6 4 7 3] - т. перестановки [ 0] [ 1 0] [ 2 1 0] [ 2 2 1 0] [ 0 2 2 1 0] [ 4 0 2 2 1 0] [ 6 4 0 2 2 1 0] [ 3 6 4 0 2 2 1 0] [2 3 6 4 0 2 2 1 0] - т. инверсии