我如何才能找到增加一定长度的子序列与二进制索引树（BIT）的总数是多少？
其实这是从问题SPOJ在线评测
例
假设我有一个数组1,2,2,10
长度为3的增加的子序列是1,2,4和1,3,4
所以，答案是2 。
Answer 1:
让：
dp[i, j] = number of increasing subsequences of length j that end at i
一个简单的解决方案是在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 。
让我们尝试另一种方法。 我们也有S -对值上限我们的数组英寸 让我们试着找到与此相关的算法。
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)很容易。 我们需要的是一个数据结构，让我们总结有效和一系列更新内容： 段树 ， 二进制树索引等。
文章来源: How to find the total number of Increasing sub-sequences of certain length with Binary Index Tree(BIT)
