我有一个问题，我需要为常量键i（也就是整数，在某个范围内，比如[1；m]）存储不断变化的数据值v_i（整数）。我需要能够快速地画出一个随机元素，这个元素的权重是v_I，也就是说，画k键的概率应该是v_I/（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；花费o（m）时间。
我现在的问题是如何优化树节点在内存中的位置，以最小化缓存未命中因为所有的键都是已知的并且保持不变，所以本质上这就是我应该为树节点分配内存的顺序。
谢谢！!
最佳答案
我不认为二叉树有一个最佳的填充顺序，除了像预排序，后排序，顺序填充之类的东西？你的问题不是在问缓存通常是如何工作的吗？不幸的是，我自己也不知道，也许在你的情况下，更简单的散列数组会更有效？
关于algorithm - 二叉树的最优填充顺序，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5727197/