Это решение O (nklogn) , где n - длина входного массива, а k - размер увеличивающихся подпоследовательностей.Он основан на решении , упомянутом в вопросе .
vector<int> values, массив длины n , который нужно искать для увеличения подпоследовательностей.
vector<int> temp(n); // Array for sorting
map<int, int> mapIndex; // This will translate from the value in index to the 1-based count of values less than it
partial_sort_copy(values.cbegin(), values.cend(), temp.begin(), temp.end());
for(auto i = 0; i < n; ++i){
mapIndex.insert(make_pair(temp[i], i + 1)); // insert will only allow each number to be added to the map the first time
}
mapIndex теперь содержит рейтинг всех чисел в values.
vector<vector<int>> binaryIndexTree(k, vector<int>(n)); // A 2D binary index tree with depth k
auto result = 0;
for(auto it = values.cbegin(); it != values.cend(); ++it){
auto rank = mapIndex[*it];
auto value = 1; // Number of sequences to be added to this rank and all subsequent ranks
update(rank, value, binaryIndexTree[0]); // Populate the binary index tree for sub-sequences of length 1
for(auto i = 1; i < k; ++i){ // Itterate over all sub-sequence lengths 2 - k
value = getValue(rank - 1, binaryIndexTree[i - 1]); // Retrieve all possible shorter sub-sequences of lesser or equal rank
update(rank, value, binaryIndexTree[i]); // Update the binary index tree for sub sequences of this length
}
result += value; // Add the possible sub-sequences of length k for this rank
}
После размещения всех n элементов values во всех k размеры binaryIndexTree.value s, собранные в result, представляют общее количество увеличивающихся подпоследовательностей длины k .
Функции дерева двоичных индексов, используемые для получения этого результата:
void update(int rank, int increment, vector<int>& binaryIndexTree)
{
while (rank < binaryIndexTree.size()) { // Increment the current rank and all higher ranks
binaryIndexTree[rank - 1] += increment;
rank += (rank & -rank);
}
}
int getValue(int rank, const vector<int>& binaryIndexTree)
{
auto result = 0;
while (rank > 0) { // Search the current rank and all lower ranks
result += binaryIndexTree[rank - 1]; // Sum any value found into result
rank -= (rank & -rank);
}
return result;
}
Дерево двоичного индекса, очевидно, O (nklogn) , но это способностьпоследовательно заполняйте его, что создает возможность использования его для решения.
mapIndex создает ранг для каждого числа в values, так что наименьшее число в values имеет ранг 1.(Например, если values равно «2, 3, 4, 3, 4, 1», тогда mapIndex будет содержать: «{1, 1}, {2, 2}, {3, 3}, {4,5} ". Обратите внимание, что" 4 "имеет ранг" 5 ", потому что есть 2" 3 "в values
binaryIndexTree имеет k различных деревьев, уровень x будет представлять общее количество увеличивающихся подстрок, которые могут быть сформированы длиной x . Любое число в values может создать подстроку длины 1, поэтому каждый элемент будетувеличивайте его ранг и все звания выше него на 1.
На более высоких уровнях увеличивающаяся подстрока зависит от того, имеется ли уже доступная подстрока более короткой длины и более низкого ранга.
Поскольку элементы вставляются в дерево двоичных индексов в соответствии с их порядком в values, порядок вхождения в values сохраняется, поэтому, если элемент был вставлен в binaryIndexTree, то есть потому, что он предшествовал текущему элементув values.
Отличное описание того, как дерево двоичных индексов доступно здесь: http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/
Вы можете найти исполняемую версию кода здесь: http://ideone.com/GdF0me