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）时间）。
现在我所面临的问题是如何优化内存中树节点的放置，以尽量减少缓存未命中。由于所有的密钥都是已知的并且保持不变，所以这基本上是我应该为树节点分配内存的顺序。
谢谢！