动态权重场景下：高效提升特定元素相对概率的方案探讨

场景与需求 #

静态权重场景下，推荐采用Walker Alias方法，它具备O(1)的采样复杂度。但当前面临需临时动态调整特定元素概率的场景：
现有初始权重映射如下：

A = 5, B = 10, C = 15, D = 20

需求为：将A的相对概率提升20%至12%，C的相对概率提升15%至34.5%。

初始调整方案 #

最初的思路是先调整A、C的权重，再按比例降低B、D的权重以保持总权重不变：

1. 调整A、C的权重：

a = 5
c = 15
newA = a * 1.2 = 6
newC = c * 1.15 = 17.25
difference = (newA - a) + (newC - c) = (6 - 5) + (17.25 - 15) = 1 + 2.25 = 3.25

2. 按比例降低B、D的权重：

b = 10
d = 20
bAndD = b + d = 30
newB = b - (b / bAndD) * difference = 10 - 1.083333333333333 = 8.916666666666667
newD = d - (d / bAndD) * difference = 20 - 2.166666666666667 = 17.83333333333333

最终权重与对应概率：

a = 6
b = 8.916666666666667
c = 17.25
d = 17.83333333333333
totalWeight = remains 50

chanceA = 12% (20% increase)
chanceB = ~17.83% (~10.83% decrease)
chanceC = 34.5% (15% increase)
chanceD = ~35.66% (~10.83% decrease)

但该方案需要更新所有元素的权重，无法适配Dynamic Walker Alias、Fenwick Tree或Segment Tree这类高效数据结构。现寻求仅修改A、C权重的更优方案，是否存在此类方案？若不存在，是否只能采用以下累加权重的采样方法：

const totalWeight = weights.reduce(
  (sum, weight) => sum + weight,
  0,
);
const randomWeight = Math.random() * totalWeight;
let cumulativeWeight = 0;
for (let index = 0; index < weights.length; index++) {
  cumulativeWeight += weights[index];
  if (randomWeight < cumulativeWeight) {
    return index;
  }
}

新的调整方案 #

后续找到一种无需修改B、D权重的方案：

Wa + Wb + Wc + Wd = Wtotal (new total weight)

desired probability:
Wa / Wtotal = 0.12
Wc / Wtotal = 0.345

Wtotal = Wa + Wc + 30
Wa = Wtotal * 0.12
Wс = Wtotal * 0.345

Wtotal * 0.12 + Wtotal * 0.345 + 30 = Wtotal
0.535 * Wtotal = 30
Wtotal = 30 / 0.535
Wtotal = 56.07476635514019

Wa = 6.728971962616822 = 12% chance
Wc = 19.34579439252337 = 34.5% chance

疑问 #

这种新方案是否能适配高效数据结构，降低更新成本？

内容的提问来源于stack exchange，提问作者user64675