How can I find the total number of Increasing sub-sequences of certain length with Binary Index Tree(BIT)?
Actually this is a problem from Spoj Online Judge
Example
Suppose I have an array 1,2,2,10
The increasing sub-sequences of length 3 are 1,2,4
and 1,3,4
So, the answer is 2
.
Let:
An easy solution is in
O(n^2 * k)
: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 to10000
.k
is small enough, so we should try to find a way to get rid of ann
.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.This has complexity
O(n * k * S)
, but we can reduce it toO(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.