algorithm - 如何用二叉索引树(BIT)查找一定长度的递增子序列总数

如何通过二叉索引树(BIT)找到一定长度的递增子序列的总数？

其实这是Spoj Online Judge的问题

示例
假设我有一个1,2,2,10数组

长度为3的递增子序列为1,2,4和1,3,4
因此，答案是2。

最佳答案

让:

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等。

关于algorithm - 如何用二叉索引树(BIT)查找一定长度的递增子序列总数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15057591/