Come trovare il numero totale di sottosequenze crescenti di una certa lunghezza con BIT Index Tree (BIT)

Question

Come posso trovare il numero totale di sottosequenze crescenti di certa lunghezza con BIT (Binary Index Tree)?

realtà questo è un problema da Spoj Online Judge

Esempio
Supponiamo di avere un array 1,2,2,10

Le crescenti sotto-sequenze di lunghezza 3 sono 1,2,4 e 1,3,4

Quindi, la risposta è 2.

Answer 1

Let:

dp[i, j] = number of increasing subsequences of length j that end at i 

Una soluzione semplice è in O(n^2 * k):

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

for i = 1 to n do 
    for j = 1 to i - 1 do 
    if array[i] > array[j] 
     for p = 2 to k do 
     dp[i, p] += dp[j, p - 1] 

La risposta è dp[1, k] + dp[2, k] + ... + dp[n, k].

Ora, questo funziona, ma è inefficiente per i vincoli specificati, poiché n può salire a 10000. k è abbastanza piccolo, quindi dovremmo provare a trovare un modo per sbarazzarsi di un n.

Proviamo un altro approccio. Abbiamo anche S - il limite superiore dei valori nel nostro array. Proviamo a trovare un algoritmo in relazione a questo.

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] 

    // 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   
     dp[i, p] += num[j] 

Questo ha complessità O(n * k * S), ma possiamo ridurlo a O(n * k * log S) abbastanza facilmente. Tutti abbiamo bisogno è una struttura dati che ci permette di Somma e in modo efficiente gli elementi di aggiornamento in un intervallo: segment trees, binary indexed trees ecc