使用BIT增加序列的数量

Question

对于EX：一个序列给出1 3 2 4现在我必须找到递增序列的数量。
我开始知道BIT算法，与O（n ）相比，我给出了O（nlog n）解。
代码是遵循

void update(int idx ,int val){ 
    while (idx <= MaxVal){ 
     tree[idx] += val; 
     idx += (idx & -idx); 
    } 
} 

要阅读

int read(int idx){ 
    int sum = 0; 
    while (idx > 0){ 
     sum += tree[idx]; 
     idx -= (idx & -idx); 
    } 
    return sum; 
} 

我不明白如何they使用BIT的算法可以请你帮我

Answer 1

二进制进行索引树的read函数将返回等于或小于idx的值的数量。

因此，通过将每个元素一个接一个，从0到n（n为元素的数量）

• 对于每个元素，我们需要知道有多少值是小于这个当前元素并且已经添加到BIT中。假设该号码为x，以便终止于该元素递增序列的数目是2^x的

• 计算，在这个元件结束的所有序列之后，我们需要把这个元素添加到BIT

伪代码：

long result = 0; 
BIT tree = //initialize BIT tree 
for(int i = 0; i < n; i++){ 
    int number = tree.read(data[i] - 1);// Get the number of element that less than data[i]; 
    result += 1L<< number; 
    tree.update(data[i], 1); 

} 

随着更新和读取功能有O（log n）的时间复杂度，上述算法中的时间复杂度为O（n log n）的