使用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）的