发现增加的子序列的数目 [英] Find the number of increasing sub sequence

问题描述

我想找到一个数组中增加子的数目，我碰到一个二进制索引树，为我们提供了 O（log n）的解决方案。

I want to find the numbers of increasing subsequence in an array and I came across a Binary index tree which provide us O(log n) solution.

我不明白用于位在code：

I can't understand the code used for BIT:

void madd(int& a, int b)
{
    a += b;
}

// fenwick code
void update(int i, int x)
{
    for (++i; i < MAX_N; i += i & -i) madd(ft[i], x);
}

int query(int i)
{
    int s = 0;
    for (++i; i > 0; i -= i & -i) madd(s, ft[i]);
    return s;
}

for (int i = 0; i < N; i++)
{
    dp[i] = 1 + query(H[i] - 1); // H[i] contains the our number array

    update(H[i], dp[i]);
}

请帮我理解这一点。
谢谢

Please help me to understand it.
Thank you

推荐答案

该算法的想法很简单：

1. 让我们创建一个数组 F ，其中 F [I] 的子序列增加的数量有我作为最后一个元素。最初，它是用零填充。

1. Let's create an array f, where f[i] is the number of increasing subsequences that has i as a last element. Initially it is filled with zeros.

让我们遍历初始阵列和更新 F 值的所有元素。如果当前元素是 ^ h ，那么我们可以把它添加到所有增加的子序列具有最后一个元素小于 ^ h 或创建一个新的亚序列，其中包含仅这个号码。这就是为什么 DP [I] = SUM（F [J]）+ 1 ，其中 0℃= J＆LT; ^ h 。

Let's iterate over all elements of the initial array and update f values. If the current element is h, then we can add it to all increasing subsequences that have the last element less than h or create a new subsequence that contains only this number. That's why dp[i] = sum(f[j]) + 1, where 0 <= j < h.

位可用于查找对数组的preFIX的款项，并更新一个元素有效（这是必需的步骤2），这就是为什么它是用来存储 F 值。

BIT can be used to find a sum on a prefix of the array and update one element efficiently(it is required for the step 2), that's why it is used to store f values.

这篇关于发现增加的子序列的数目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！