How to find the total number of Increasing sub-sequences of certain length with Binary Index Tree(BIT)

algorithm, binary-indexed-tree, data-structures, fenwick-tree, sequence

Solution

Let:

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

An easy solution is in `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]

The answer is `dp[1, k] + dp[2, k] + ... + dp[n, k]`.

Now, this works, but it is inefficient for your given constraints, since `n` can go up to `10000`. `k` is small enough, so we should try to find a way to get rid of an `n`.

Let's try another approach. We also have `S` - the upper bound on the values in our array. Let's try to find an algorithm in relation to this.

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]

This has complexity `O(n * k * S)`, but we can reduce it to `O(n * k * log S)` quite easily. All we need is a data structure that lets us efficiently sum and update elements in a range: segment trees, binary indexed trees etc.

Problem

Original source