Meta 加权随机抽样：前缀二分到Alias常数查询

题目重点：按城市人口或给定权重随机选择下标，比较百万次调用时的预处理与查询成本。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

权重为非负整数且总和W>0，零权重元素永不被选；城市标签与权重下标对应，返回标签可在外层映射。
随机源randbelow(b)须在[0,b)均匀；示例可注入随机函数，支持独立遍历全部ticket验证，不把单次模拟频率当证明。
权重固定的训练实现一次预处理；Alias是高频调用优化选择，不假设所有题都要求知晓此算法。

解题路线

前缀法构建累计权重prefix。抽ticket∈[0,W)，用bisect_right找第一个prefix>ticket，重复前缀对应零权重自然被跳过。每个元素占恰好w_i个整数ticket，概率w_i/W。
Alias把n列容量均设W，总票空间nW；原元素配额为n×w_i。把小列s补齐到W，缺口来自大列l；threshold[s]保留s票数，其余alias到l，再扣l配额并重新分组。
查询均匀选列，再在[0,W)抽ticket；小于threshold取本列，否则取alias。按所有列总贡献守恒，每元素仍占n×w_i票，所以概率w_i/W，无浮点阈值舍入。
选型看更新次数与抽样次数：prefix预处理O(n)、每次O(log n)；Alias预处理O(n)、每次O(1)，但修改权重常需重建。频繁更新用Fenwick维护总权并二分定位。

手动走一遍

权重[1,0,3]，prefix=[1,1,4]，ticket0→0、1/2/3→2。Alias全体3×4=12个(列,ticket)组合中元素0占3个、元素1占0个、元素2占9个，精确得到1/4与3/4。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from bisect import bisect_right
from random import randrange


class WeightedSampler:
    """Nonnegative integer weights. Inject randbelow(bound) for reproducible tests."""
    def __init__(self, weights):
        if not weights or any(not isinstance(w, int) or w < 0 for w in weights) or sum(weights) <= 0:
            raise ValueError("positive total of nonnegative integer weights required")
        self.total = sum(weights)
        self.prefix = []
        running = 0
        for w in weights:
            running += w; self.prefix.append(running)
        n = len(weights)
        scaled = [w * n for w in weights]
        small = [i for i, value in enumerate(scaled) if value < self.total]
        large = [i for i, value in enumerate(scaled) if value >= self.total]
        self.threshold = [self.total] * n
        self.alias = list(range(n))
        while small and large:
            s, l = small.pop(), large.pop()
            self.threshold[s] = scaled[s]
            self.alias[s] = l
            scaled[l] -= self.total - scaled[s]
            (small if scaled[l] < self.total else large).append(l)

    def sample_prefix(self, randbelow=randrange):
        return bisect_right(self.prefix, randbelow(self.total))

    def sample_alias(self, randbelow=randrange):
        column = randbelow(len(self.alias))
        ticket = randbelow(self.total)
        return column if ticket < self.threshold[column] else self.alias[column]

复杂度

prefix与Alias均O(n)预处理和空间；Q次查询分别O(n+Q log n)及O(n+Q)。Python大整数成本还随权重bit长度变化，不能将任意长度整数的操作一律视为实际常数。

易错点与追问

容易失分的边界

抽randint(0,W)会多出一个端点，ticket=W无合法元素；必须半开范围。
负权重、全零权重或空列表无法定义概率，应拒绝而非随便返回。
用浮点累计巨量权重可能丢小概率类别；整数配额更容易精确验证。

继续深挖

若权重按秒变化，考虑树状数组O(log n)更新/查询而非每次重建Alias。
不放回加权抽样不是反复调用此接口后去重；需要每选一次减权/改状态或专门算法。