1
我有一個問題，我需要爲常量鍵i（也是整數，在一些範圍中說[1; M]）存儲不斷變化的數據值v_i（整數）。我需要能夠快速繪製一個由值v_i加權的隨機元素，即繪製關鍵字k的概率應該是v_k /（sum（i = 1 ... M）v_i）二叉樹的最佳填充順序
最好的想法，我可以提出使用一棵二叉樹並且將以k爲根的子樹中的值的部分和存儲爲密鑰k的值（仍然在範圍[1; M]中）。然後，每當一個值發生變化時，我需要更新它的節點和樹中的所有父節點（由於密鑰是固定的，因此二叉樹是完全平衡的，因此需要O（log M）時間）。如上所示繪製一個隨機元素也需要O（log M）時間（對於樹的每個級別，比較範圍（0,1）內的隨機數與左子樹，右子樹和節點本身），並且比原始算法快得多（採用隨機數r，遍歷元素以找到最小k，使得sum（i = 1 ... k）< r，sum（i = 1 ... k +1）> r;需要O（M）時間）。
現在我所面臨的問題是如何優化內存中樹節點的放置，以儘量減少緩存未命中。由於所有的密鑰都是已知的並且保持不變，所以這基本上是我應該爲樹節點分配內存的順序。
謝謝！