Изменения
Нет описания правки
Сложность представленного алгоритма есть <tex>O(n\log n)</tex>. Алгоритм с такой же сложностью можно построить с помощью [[Дерево_отрезков._Построение | дерева отрезков.]]
== Алгоритм построения за O(N) ==
Для построения таблицы инверсий за линейное время воспользуемся карманной сортировкой. Известно что карманная сортировка имеет линейную сложность, но только в том случае если элементы равномерно распределены. Т.к. мы ищем кол-во инверсий в перестановке то мы знаем что наши элементы встречаются единожды , а следовательно равномерно распределены. При карманной сортировке нужно определить карман '''B''', в который попадет текущий элемент. Затем найти количество элементов в старших карманах относительно '''B'''. Потом аккуратно подсчитать количество элементов, больших текущего в кармане '''B'''. Карман '''A''' считается старшим для кармана '''B''', если любой элемент из '''A''' больше любого элемента из '''B'''.
<font color=green>MAX - число больше a.size() и из которого можно извлечь целый квадратный корень.</font>
<font color=green>BUCKET - размер кармана BUCKET=sqrt(MAX)</font>
'''int''' bucket_sort( '''vector<int>''' a )
'''int''' ans = 0;<font color=green>//изначально кол-во инверсий</font>
'''vector<int>''' tab_invers(a'''.size()'''+1);<font color=green>//таблица перестановок</font>
'''vector< list<int> >''' mem(BUCKET);
'''for'''('''int''' i = 0;i < a'''.size()''' ; i++)
'''int''' invers = 0; <font color=green>//кол-во инверсий которые создает элемент a[i]</font>
'''int''' pos = (a[i] - 1)/(MAX / BUCKET);<font color=green>//Определяем в каком кармане должен лежать элемент</font>
'''list<int>::iterator''' it = mem[pos]'''.begin()''';
'''int''' newpos = 0;
'''while'''(it != mem[pos]'''.end()''' && (*it) < a[i] ) <font color=green>//идем до позиции где должен стоять элемент</font>
it++;
newpos++;
invers += mem[pos]'''.size()''' - newpos;<font color=green>//ищем сколько инверсий эленент создает в своем кармане</font>
mem[pos]'''.insert'''( it , a[i] );<font color=green>//вставляем элемент в список</font>
'''for'''('''int''' i = pos + 1 ; i < BUCKET ; i++) <font color=green>//ищем сколько инверсий он создает с элементами в других карманах</font>
invers += mem[i]'''.size()''';
tab_invers[a[i]] = invers;
ans += invers;
'''return''' tab_invers;
'''return''' ans;
Утверждается, что cложность представленного алгоритма есть <tex>O(n)</tex>.
== Алгоритм восстановления ==
