動態（即可變大小）Fenwick樹？

問題： 我偶然發現了Fenwick樹（二叉樹索引樹），可以很容易計算出累積和。但是，我只發現leeves（加法）數量不變的實現（但它們的值可以改變）。 有沒有像一個泛化的Fenwick樹，允許改變leeeves（加數）的數量，即有一個可變的大小？動態（即可變大小）Fenwick樹？

背景我目前正在寫一些隨機模擬代碼（在C++）：有在甕球和每個滾珠i具有一定的概率P_I要繪製。在一次抽籤活動中，球會被抽出（並被移除），並被新的概率所替換爲兩個新球（並且所有的概率都會相應地重新調整;我已經這樣做了「重新調整比例」，所以不用擔心）。在某個時候，我開始去除球，使得球的數量以恆定值（之前已知）波動。要高效地繪製圖畫，我想使用二叉樹。標準的芬威克樹正是我想要的，只是它不允許在甕中的球數量發生變化。

典型數字 開始用10個球，添加球並開始一次移除球有大約1000使得存在然後在甕900和1100之間的滾珠（即球被添加和去除，使得數保持在1000左右）。

解決方法到目前爲止 估算的最大數目需要球（有一些安全餘量，說1200個球），使大型大多數球的初始具有概率0要繪製的固定尺寸分域樹正在不斷更新。

非常感謝您的幫助！ Matthias

來源

2014-02-24 matthse

實際上，正常的（不以任何方式推廣）Fenwick樹允許隨時增加葉子的數量。

某些特定的實現可能不允許。但這可能是固定的。例如，implementation from TopCoder不允許更改樹葉的數量。問題是update函數修改從給定索引開始並向上的數組元素，當它達到某個極限（MaxVal）時停止，這在我們的例子中是未知的。函數迭代數組元素向下，所以它不需要知道當前數組的大小。如果我們換update和read之間陣列迭代代碼，這個問題可能是固定的：現在update並不需要知道MaxVal，MaxVal在read被使用，我們可以使用最大更新的索引，只要MaxVal。

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

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

備註。

與TopCoder的實現（其中read返回前綴和）不同，此實現給出了後綴sum。如果您需要前綴總和，只需從總值中減去read返回的值。我選擇了這個實現，因爲（1）它是一個着名的TopCoder實現的簡單修改，（2）它以非常對稱的方式更新索引，因此只需將'+'更改爲' - '即可從前綴到後綴。
否則，我寧願在索引計算中使用不同的按位操作。恕我直言，這個博客：Fenwick trees demystified建議一個更好的選擇，每索引更新只有2個操作，而不是3（但也需要一些修改，以允許可變大小）。如果兼容性不是問題，我們可以通過使用一些特定的指令，如最近Intel指令集（BMI1）的BLSR來做得更好。

來源

2014-02-24 19:09:31

動態（即可變大小）Fenwick樹？

回答

相關問題