如何使用二进制索引树（BIT）查找一定长度的增加子序列的总数 [英] How to find the total number of Increasing sub-sequences of certain length with Binary Index Tree(BIT)

问题描述

如何使用二进制索引树（BIT）找到一定长度的增加子序列的总数？

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

其实这是一个问题，从 Spoj在线判断

Actually this is a problem from Spoj Online Judge

示例

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

长度为3的子序列越来越多， 1,2,4 和 1,3,4

The increasing sub-sequences of length 3 are 1,2,4 and 1,3,4

所以答案是 2 。

推荐答案

让我们：

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

一个简单的解决方案是在 O（n ^ 2 * k） code>：

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]

答案是 dp [1，k] + dp [2，k] + ... + dp [n，k] 。

现在，这是有效的，但是对于给定的约束来说效率低下，因为 n 最高可达 10000 。 k 足够小，所以我们应该尝试找到一种方法来摆脱一个 n 。

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.

我们来试试另一种方法。我们也有 S - 数组中值的上限。我们尝试找到一个与此相关的算法。

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]

这有复杂性 O（n * k * S），但是我们可以将其减少到 O（n * k * log S）很容易。我们需要的是一个数据结构，可以让我们有效地总结和更新范围内的元素：分段树，二进制索引树等。

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.

这篇关于如何使用二进制索引树（BIT）查找一定长度的增加子序列的总数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！