如何找到哪個位置在BIT中有前綴總和M？

Question

假設我創建了一個前綴長度爲N的二進制索引樹。主陣列僅包含0 s和1 s。現在我想找到哪個索引有一個前綴總和M（這意味着正好有M 1 s）。

像我的數組是a[]={1,0,0,1,1};

前綴和會是什麼樣{1,1,1,2,3};

現在第三屆指數（0基於）具有2

前綴和我如何才能找到這個指數有幾分？

在此先感謝。

Answer 1

爲什麼你不能對該索引進行二分法搜索？這將需要O(log n * log n)時間。下面是一個簡單的實現 -

int findIndex(int sum) { 
    int l = 1, r = n; 
    while(l <= r) { 
     int mid = l + r >> 1; 
     int This = read(mid); 
     if(This == sum) return mid; 
     else if(This < sum) l = mid+1; 
     else r = mid-1; 
    } return -1; 
} 

我用了read(x)功能。那應該在O(log n)時間內返回間隔[1,x]的總和。整體複雜度將爲O(log^2 n)。
希望它有幫助。

Answer 2

如果數組a[n]中的元素是非負數（前綴和數組p[n]是非遞減的），則可以通過前綴sum查找一個元素作爲查詢前綴和，該索引來自BIT，這需要O（logn）時間。唯一的區別是，您需要比較每個級別獲得的前綴總和與您的輸入以確定隨後需要搜索哪個子樹 - 如果前綴總和小於您的輸入，則繼續搜索左側子樹;否則，搜索右邊的子樹;重複這個過程直到到達一個總結所需前綴和的節點，在這種情況下返回節點的索引。這個想法類似於二分法搜索，因爲前綴總和在BIT中自然排序。如果a[n]中存在負值，則此方法將不起作用，因爲在此情況下，BIT中的前綴總和不會被排序。