c++ - 长度为 k 的递增子序列数

Question

我试图理解在时间 O(nklog(n)) 内给出数组中长度为 K 的递增子序列数的算法。我知道如何使用 O(k*n^2) 算法解决同样的问题。我查了一下，发现这个解决方案使用 BIT (Fenwick Tree) 和 DP。我也找到了一些代码，但我一直无法理解。

以下是我访问过的一些有用的链接。

Here in SO
Topcoder forum
Random webpage

如果有人能帮助我理解这个算法，我将不胜感激。

Answer 1

我正在从 here 复制我的算法，其中解释了其逻辑:

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 数组上的以下操作:

• 给定 (x, v) 将 v 添加到 num[x] (与 *1* 相关);
• 给定 x，求和 num[1] + num[2] + ... + num[x](与 *2* 相关).

对于这两种数据结构来说，这些都是微不足道的问题。

注意:这将具有 O(n*k*log S) 的复杂度，其中 S 是中值的上限你的阵列。这可能不够好，也可能不够好。要使其成为 O(n*k*log n)，您需要在运行上述算法之前规范化数组的值。规范化意味着将所有数组值转换为小于或等于 n 的值。所以这个:

5235 223 1000 40 40

变成:

4 2 3 1 1

这可以通过排序来完成(保留原始索引)。