Изменения

Для восстановления таблицы перестановки из по таблицы инверсий создаем таблицу, которую будем расширять, по мере добавления в неё чисел. Добавляем в эту таблицу число <tex>iT</tex> (где воспользуемся следующим соображением: единица стоит на <tex>iT_i</tex> от <tex>n-ом месте (индексируем элементы с нуля), так как остальные числа в перестановке больше единицы. Далее, если известны расположения всех чисел </tex> до 1) на позицию <tex>, \dots, k+1</tex>, где то число <tex>k+ 1</tex> - число в таблице инверсий стоит на <tex>iT_{k + 1}</tex>-том месте. Данный алгоритм довольно прост в реализации, но без использования дополнительных структур данныхой ещё не занятой позиции: все числа, имеет сложность меньшие <tex>O(n^2)k + 1</tex>, т. куже расставлены. для вставки элемента Это рассуждение напрямую переписывается в определённую позицию, требуется порядка <tex>n</tex> перестановок элементов.код следующим образом:

Приведём алгоритм восстановления с использованием [[Сортировка слиянием|сортировки слиянием]] def recover_straight(ls): n = len(ls) result = array(0, n) curr = 1 for k in ls: j = 0 for (i = 0, имеющий сложность i <tex>O(n\log_2n, i += 1)</tex>.: if result[i] == 0: if j == k: result[i] = curr break else: j += 1 curr += 1 return result

Пусть <tex>\alpha</tex> и <tex>\beta</tex> - цепочки упорядоченных пар целых неотрицательных чисел <tex>[m_1, n_1]\dots[m_k, n_k]</tex>. Рассмотрим двоичную операцию <tex>\circ</tex>, рекурсивно определенную на парах таких цепочек следующим образом:* j — счётчик пропущенных свободных позиций $([m, n]\alpha)\circ([m', n']\beta)=\left\{\begin{aligned}[]* k — количество инверсий слева для элемента curr [m* result — массив,n](\alpha \circ ([m'-m, n']\beta)), m \le m',\\ [m', n'](([m-m'-1, n]\alpha) \circ \beta)в который записывается перестановка. Равенство элемента массива нулю обозначает, m>m'.\\ \end{aligned} \rightчто эта позиция свободна.$

Сопоставим каждому элементу таблицы инверсий его номер. Получится множество упорядоченных пар чисел Этот простой алгоритм имеет сложность <tex>[m_1, n_1]\dots[m_k, n_k]O(n^2)</tex>, где — внутренний цикл делает до <tex>m_in</tex> {{---}} сам элементитераций, а <tex>n_i</tex> {{---}} его номер. Разобьём данные элементы на пары и произведём с ними операцию <tex>\circ</tex>. Получим некоторое количество цепочек упорядоченных пар. Также разбиваем их на пары и производим операцию внешний — ровно <tex>\circn</tex>. Так действуем, пока не останется одна цепочка. Выписывая вторые элементы данных упорядоченных пар в том порядке, в каком они представлены в цепочке, получим первоначальную перестановкуитераций.

Цепочка наподобие <tex>[4, 4][1Видно,3]</tex> представляет "_ _ _ _ 4 _ 3 _ что для восстановления нужно узнавать <tex>\inftyk</tex>"-ую свободную позицию. Это можно делать с помощью дерева отрезков следующим образом: построим дерево отрезков для суммы на массиве из единиц. Единица в позиции означает, где "_" означает пропускчто данная позиция свободна. Операция Чтобы найти <tex>\alpha \circ \betak</tex> вставляет пропуски и заполнения из -ую свободную позицию, нужно спускаться (начиная с корня) в левое поддерево если сумма в нём больше, чем <tex>\betak</tex> на место пропусков , и в <tex>\alpha</tex>правое дерево иначе.

* <tex>[4 def recover(inv): n = len(inv) tree = build_segment_tree(array(n, 1, 6, 3, 2, 2, )) result = array(n) curr = 1, 1, 1, 0] for k in inv: node = tree.root while (!node.is_leaf): if (k </tex> node.value): node = node.left else: k - таблица инверсий= node.left.value* <tex>[4,1]\circ[1,2], [6,3]\circ[3,4], [2,5]\circ[2,6], [1,7]\circ[1,8], [1,9]\circ[0,10]</tex> node = node.right* <tex> result[1,2][2,1]\circ[3,4][2,3], [2,5][0,6]\circ[1,7][0,8], [0,10][0,9node.index]</tex>= curr* <tex>[1,2][2, node.add(-1][0,4][2,3]\circ[1,7][0,5][0,6][0,8], [0,10][0,9]</tex>)* <tex>[ curr += 1,2][0,7][0,5][0,1][0,4][0,6][0,8][0,3]\circ[0,10][0,9]</tex>* <tex>[0,10][0,2][0,7][0,5][0,1][0,4][0,6][0,8][0,3][0,9]</tex> return result

Получаем перестановку * build_segment_tree — строит дерево отрезков над массивом* node — вершина дерева* node.index — индекс соответсвующего элемента в массиве для листа дерева Этот алгоритм имеет сложность <tex>[10O(n \log n)</tex>: делается <tex>n</tex> итераций цикла, 2в которой происходит спуск по дереву высоты <tex>O(\log n)</tex> и один запрос на дереве отрезков. Таким образом, 7, 5, 1, 4, 6, 8, 3, 9]время работы алгоритма на каждой итерации есть <tex>O(\log n)</tex>.