バイナリインデックスツリー（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など