水桶的索引計數

Question

所以，這是我的小問題。

比方說，我有一個水桶0 _的列表...一個_ň分別含有L- < = C 。C _ň < H項。我可以決定L和H的限制。我甚至可以動態更新它們，但我認爲它不會有多大幫助。

桶的順序很重要。我不能去交換他們。

現在，我想這些指標桶，因此：

• 我知道項目總數
• 我可以查找第i個元素
• 我可以添加/刪除項目從任何存儲桶中更新索引

看起來很簡單吧？看到這些標準，我立即想到了芬威克樹。這就是他們的真正意義。

然而，當你想使用的情況下，其他幾個用例蠕變：

• 如果一個桶計數低於L，桶必須消失（不用擔心物品還）
• 如果一個桶計數達到H，則必須創建一個新的水桶，因爲這是一個充滿

我還沒有想出如何有效地編輯樹狀數組：刪除/添加一個節點，而無需重建整棵樹...

當然，我們可以設置L = 0，這樣刪除將變得不必要，但添加項目不能真正避免。

因此，這裏的問題：

你知道無論是對本索引或如何更新樹狀數組結構更合理？

主要關心的是效率，而且因爲我打算實施緩存/內存考慮值得擔心。

背景：

我想拿出有點類似於B-樹的結構和排名跳躍表，但有局部索引。這兩個結構的問題是索引是沿着數據保存的，這在緩存方面效率低下（即，您需要從內存中獲取多個頁面）。數據庫實現表明，保持索引與實際數據隔離更容易緩存，從而更高效。

Answer 1

我明白你的問題爲：

每個桶有一個內部的秩序和水桶本身具有的訂單，因此，所有的元素有一定的順序，你需要在排序中第i個元素。

要解決：

你可以做的是保持一個「累積值」樹的葉子節點（X1，X2，...，xn）映射是桶的大小。節點的值是其直接子節點的值的總和。保持2的冪將使其變得簡單（最終可以用零大小的桶填充它），並且該樹將是完整的樹。

對應於每個存儲桶，您將維護一個指向相應葉節點的指針。

例如，桶大小是2,1,4,8。

樹看起來像

 15 
    /\ 
    3 12 
/\/\ 
2 1 4 8 

如果你想的總數，讀取根節點的值。

如果您想要修改某些xk（即更改相應的桶大小），您可以沿着父指針走向樹，更新值。

例如，如果你添加4項第二桶將是（標有*的節點是改變了的）

 19* 
    / \ 
    7* 12 
/\ /\ 
2 5* 4 8 

如果你想找到的第i個元素，你走在上面的樹，有效地進行二分查找。你已經有了一個左小孩和右小孩。如果i>留下當前節點的子節點值，則減去左側子節點值並在右樹中遞歸。如果我< =左邊的子節點值，你往左走再次遞歸。

說你想找到在上面的樹中的第9個元素：

由於根的左孩子是7 您從9減去7（獲得2）和向右走。

由於2 < 4（12的左邊孩子），你走了。

您位於第三個存儲桶對應的葉節點。您現在需要選擇該存儲桶中的第二個元素。

如果你不得不添加一個新桶，你可以通過添加一個新的根來增加樹的大小（如果需要的話），使現有的樹成爲左邊的子樹，並添加一個新的樹，添加（我們是新樹的最左邊的葉子）。這將在O（1）時間內向樹添加新值。警戒是你最後只能添加一個桶，而不是中間的任何地方。

獲取總數爲O（1）。 更新單個桶/查找項目是O（logn）。

添加新存儲桶是攤銷O（1）。

空間使用量爲O（n）。

而不是二叉樹，你可以做一個B樹。

Answer 2

我仍然希望得到答案，但這裏是我可以出現在目前爲止，以下@Moron建議。

顯然我的小Fenwick樹想法不能輕易適應。在fenwick樹的末端添加新桶很容易，但不是在中間，因此這是一種失敗的原因。

我們剩下2個數據結構：二進制索引樹（具有諷刺意味的是芬威克用來描述他的結構）和排名跳過列表。

通常情況下，這不會將數據從索引中分離出來，但是我們可以得到的這種行爲：

1. 使用間接：由節點持有的元素是指向一斗，挖鬥本身
2. 使用池分配，使得指數的元素，儘管彼此獨立分配，仍接近存儲內容應有助於緩存

我傾向於選擇跳錶爲二進制樹，因爲它們是自組織，所以我是溫泉紅色不斷重新平衡我的樹的麻煩。

這些結構將允許到達O(log N)中的第i個元素，我不知道是否有可能獲得更快的漸進性能。

另一個有趣的實現細節是我有一個指向這個元素的指針，但其他可能已經插入/刪除了，我怎麼知道我的元素的排名？

如果存儲桶指向擁有它的節點，則可能會發生這種情況。但是這意味着節點不應該移動，或者應該在移動時更新桶的指針。