我想了解的算法，让我增加了长度为K的子序列在阵列中的时间为O数（N * K *的log（n））。我知道如何使用O（K * N ^ 2）算法来解决这个同样的问题。我已经看过了，发现了该解决方案采用BIT（分域树）和DP。我也发现了一些code，但我一直无法理解它。

I am trying to understand the algorithm that gives me the number of increasing subsequences of length K in an array in time O(n*k*log(n)). I know how to solve this very same problem using the O(k*n^2) algorithm. I have looked up and found out this solution uses BIT (Fenwick Tree) and DP. I have also found some code, but I have not been able to understand it.

下面是一些环节，我访问过的是有帮助的。

Here are some links I've visited that have been helpful.

在这里，在SO 上衣codeR论坛 随机网页

Here in SO Topcoder forum Random webpage

我真的AP preciate如果有些能帮助我了解该算法。

I would really appreciate if some can help me out understand this algorithm.

推荐答案

我从复制我的算法here,其中，它的逻辑解释：

I am reproducing my algorithm from here, where its logic is explained:

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] *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 *2*       
      dp[i, p] += num[j]

您可以优化 * 1 * 和 * 2 * 用段树或二进制索引树。这些将被用于有效地处理 NUM 阵列上的如下操作：

You can optimize *1* and *2* by using segment trees or binary indexed trees. These will be used to efficiently process the following operations on the num array:

这些都是为数据结构的琐碎问题。

These are trivial problems for both data structures.

注意：这将产生复杂 O（N * K *登录S），其中取值的上限在数组中的值。这可能会或可能不够好。为了让 O（N * K * log n）的，你需要正常化阵列的价值才能运行上面的算法。规范化是指将所有的数组值到值小于或等于 N 。所以这样的：

Note: This will have complexity O(n*k*log S), where S is the upper bound on the values in your array. This may or may not be good enough. To make it O(n*k*log n), you need to normalize the values of your array prior to running the above algorithm. Normalization means converting all of your array values into values lower than or equal to n. So this:

5235 223 1000 40 40

变成了：

4 2 3 1 1

这可以完成与排序（保留原有索引）。

This can be accomplished with a sort (keep the original indexes).