高效模拟滚动加权骰子（或遍历加权图），并进行频繁更新

我认为您可以使用log（k）复杂度来做到这一点，其中k是骰子中的面孔数量。

对于一个特定的节点，令p1，p2，…，pk为相对概率。令p1 + p2，…，+ pk = p。

用这些相对概率作为叶子构造一个树结构。每个非叶节点的父节点是其子节点的相对概率之和。要“掷骰子”，请在0到p之间绘制一个随机值，然后沿着树进行跟踪。当您想要更新骰子面的相对概率时，只需更改相应的叶子节点值并将其传播到整个树中即可。

这样，您可以选择一个具有一个随机数的随机值，并需要log（k）个步骤来查找与该随机数相对应的叶子，并且在更新一个叶子时，需要花费log（k）时间来更新树。

这是解决方案的非常简单的描述，如果您需要完整的描述，请告诉我。我确定它可以工作，但是不确定这是否足够满足您的需求。

概括地说，该算法需要：1.仅一个介于0和p之间的随机数2. O（log（k））复杂度以“掷骰子”（即找到下一个节点），其中k是骰子中的面孔数量3.
O（log（k））以“更新给定节点的骰子”。如果原始节点有m条边，则复杂度为O（log（k1））+ O（log（k2））…
O（（km）），其中k1，k2，… km是相邻节点的连通性节点。

====Tree Example====

如果骰子有4个面且相对概率为1：50、2：80、3：20、4：70，则按以下方式构造树：

          220       /           130         90   /         /     50    80    20    70  |    |     |      |  1    2     3      4

生成介于0到220之间的随机数v。如果它是v =100：沿左边的路线（因为100<130）然后沿右边的路线（因为100> 80）并更新v = v-80
= 20。我们在叶子声明o / p即2

如果v = 210：左且v = v-130 = 80，左v = v-70 = 10，返回leaf = 4

如果4更改为60，则将70更改为60，将90更改为80，然后将220更改为210。

==== Lazy update variation ====

无论何时更改权重，都不要立即更新树。相反，只需将其标记为“脏重”，直到需要从该特定节点进行预测。

当您需要从特定节点进行预测并且某些权重不合理时，请选择a。仅使用脏节点或b更新树。更新整个树。如果脏权重数为t且总权重数为k，则如果t *log（k）<k，则仅更新对应于脏权重（t * O（k））的树，否则更新整棵树（O（ k））。