algorithm - バイナリ インデックス ツリー (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)必要なのは、範囲内の要素を効率的に合計および更新できるデータ構造だけです:セグメント ツリー、バイナリ インデックス付きツリーなど。