如何找到使用二进制索引树（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等