如何找到使用二進制索引樹（BIT）增加特定長度的子序列的總數

Question

如何使用二進制索引樹（BIT）找到具有特定長度的增加子序列的總數？

實際上這是從Spoj Online Judge

的問題實施例
假設我有一個數組1,2,2,10

長度3是1,2,4和1,3,4

所以，答案的增加的子序列是2。

Answer 1

令：

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

一個簡單的方法是在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] 

答案是dp[1, k] + dp[2, k] + ... + dp[n, k]。

現在，這種方法很有效，但由於n可能會高達10000，因此它效率低下。 k足夠小，所以我們應該試着找到一種方法來擺脫n。

讓我們試試另一種方法。我們也有S - 數組中值的上限。我們試着找到一個與此相關的算法。

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] 

這有複雜O(n * k * S)，但我們可以把它降低到O(n * k * log S)很容易。我們需要的是一個數據結構，它可以讓我們高效地求和和更新一個範圍內的元素：segment trees,binary indexed trees等