Liczba rosnących następstw długości k

Question

Próbuję zrozumieć algorytm, który daje mi liczbę wzrastających subsekwencji długości K w tablicy w czasie O (n k log (n)). Wiem, jak rozwiązać ten sam problem za pomocą algorytmu O (k * n^2). Sprawdziłem i odkryłem, że to rozwiązanie wykorzystuje BIT (Fenwick Tree) i DP. Znalazłem również kod, ale nie byłem w stanie go zrozumieć.

Oto kilka linków, które odwiedziłem, które były pomocne.

Here in SO
Topcoder forum
Random webpage

będę naprawdę wdzięczny jeśli ktoś może mi pomóc zrozumieć ten algorytm.

Answer 1

Jestem odtwarzając mój algorytm z here, gdzie jego logika jest wyjaśnił:

dp[i, j] = same as before num[i] = how many subsequences that end with i (element, not index this time) 
     have a certain length 

for i = 1 to n do dp[i, 1] = 1 

for p = 2 to k do // for each length this time num = {0} 

    for i = 2 to n do 
    // note: dp[1, p > 1] = 0 

    // how many that end with the previous element 
    // have length p - 1 
    num[ array[i - 1] ] += dp[i - 1, p - 1] *1* 

    // append the current element to all those smaller than it 
    // that end an increasing subsequence of length p - 1, 
    // creating an increasing subsequence of length p 
    for j = 1 to array[i] - 1 do *2*  
     dp[i, p] += num[j] 

można zoptymalizować *1* i *2* za pomocą binarnych drzew segmentu lub indeksowanych drzew. Zostaną one wykorzystane efektywnie przetwarzać następujące operacje na tablicy num:

• Biorąc (x, v) dodać v do num[x] (dotyczy *1*);
• Biorąc pod uwagę x, znajdź sumę num[1] + num[2] + ... + num[x] (dotyczy *2*).

To są trywialne problemy dla obu struktur danych.

Uwaga: ten będzie miał złożoność O(n*k*log S), gdzie S jest górną granicą wartości w macierzy. To może, ale nie musi być wystarczająco dobre. Aby to zrobić, musisz znormalizować wartości swojej macierzy przed uruchomieniem powyższego algorytmu. Normalizacja oznacza konwersję wszystkich wartości tablicy na wartości mniejsze lub równe n. Więc tak:

5235 223 1000 40 40 

Staje:

4 2 3 1 1 

Można to osiągnąć z pewnego rodzaju (zachować oryginalne indeksy).