我想找到一个数组中增加子的数目，我碰到一个二进制索引树，为我们提供了 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
推荐答案该算法的想法很简单：
让我们创建一个数组 F ，其中 F [I] 的子序列增加的数量有我作为最后一个元素。最初，它是用零填充。
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.
更多推荐
发现增加的子序列的数目
发布评论