能否请您提供允许O(logN)（或至少允许O(sqrtN)）进行以下操作的数据结构：
ID（int64_t）和health（double）的项目IDhealth首选语言是C ++或C。通过加权随机，我的意思是：
考虑一下totalHealth=Sum(health[0], health[1], ..., health[N-1])。我需要快速的操作（如上所述），该操作等效于：
const double atHealth = rand_uint64_t()*totalHealth/numeric_limits<uint64_t>::max();i=0 to N-1寻找第一个i这样的Sum(health[0], health[1], ..., health[i]) >= atHealth约束：health[i] > 0，rand_uint64_t()返回介于0和之间的均匀分布的整数值numeric_limits<uint64_t>::max()。
到目前为止，我尝试过的是一种C ++ unordered_map，它允许Θ(1)通过进行快速（）插入ID和使用进行删除ID，但是操作＃3仍然是线性的，N如上面我的伪代码中所述。
非常感谢您的帮助！
我无法想到使用现有STL容器执行此操作的方法，但是如果您愿意编写自己的二进制树，则可以考虑执行此操作。诀窍在于，每个节点都将保持其左侧所有节点的总体运行状况（不必担心右侧的节点，如下所示）。然后，如果按ID顺序遍历树，则还可以按ID顺序及时计算“累积健康状况” log(n)。因此，该树按ID和累积运行状况排序，您可以log(n)按ID或“累积运行状况”及时进行查找。例如，考虑一个非常简单的树，如下所示：
ID: 8
h: 10
chl: 15
+-------|--------+
| |
ID: 4 ID: 10
h: 15 h: 7
chl: 0 chl: 0
上面的h是节点的运行状况，并且chl是节点剩余所有节点的累积运行状况。因此，以上所有节点的总运行状况为15 + 10 + 7 = 32（尽管您也可以正确地跟踪节点的累积运行状况，而您并不需要这样做，但我假设您单独维护该计数）。我们来看3种情况：
atHealth < 15。然后，在第一个节点处，您可以看到您的值小于，chl因此您知道需要左移，最终到达正确的叶子。atHealth >= 15 < 25就知道它大于15，所以您不会在根上向左走，您所在的节点的运行状况为10到10 + 15意味着该节点的累积运行状况在15到25之间，因此您表现良好。atHealth >= 25。每次您访问一个节点并向右走时，都必须添加您所在节点的chl和h，以在走树时继续计算累积健康状况，这样您就知道从10 + 25 = 25正确的位置开始，并将其添加到h或chl之后遇到的任何节点。因此，您可以快速找到右侧的节点是正确的节点。当您插入新节点时，您在遍历树时会增加每个父节点的总运行状况，而在删除节点时，您会从总运行状况中减去后退到树上。因此，插入和删除仍然是静止的O(log(n))，按ID进行的查找也log(n)可以按ID或按进行查找atHealth。
如果您想维护一棵平衡的树，事情显然会变得更加复杂，但是它仍然是可行的。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句