按权重随机选择

最直觉的做法是「按权重摊开」：1 个 0、3 个 1、2 个 2 →[0,1,1,1,2,2]，再均匀随机挑一个。思路对，但权重一大(几万)就会撑爆内存——得想个不真摊开的办法。

不真摊开，而是想象一条长度为 6 的数轴：[1] 占 (0,1]、[1] 占 (1,4]、[2] 占 (4,6]。区间越长越容易被命中——这正好等于按权重选。找「点落在哪段」用前缀和记区间右端、用二分定位。

原始权重 w：先把权重数组摆出来：[1, 3, 2]。接下来要把它累加成前缀和数组——也就是每个下标在数轴上的右端坐标。

前缀和 · 第 0 格：新建一个前缀和数组 pre。第 0 格直接抄 w[0]：pre[0]=1。它表示下标 0 的区间右端 = 1，即区间 (0,1]。

前缀和 · 第 1 格累加：第 1 格 = 前一格 pre[0]=1 加上 w[1]=3，得 pre[1]=4。下标 1 的区间右端 = 4，即区间 (1,4]，长度正好是它的权重 3。

前缀和 · 第 2 格累加：第 2 格 = pre[1]=4 加上 w[2]=2，得 pre[2]=6。这也是总权重。下标 2 占区间 (4,6]，长度 2。前缀和数组建好了：[1,4,6]。

前缀和数组 = 数轴右端：现在 pre=[1,4,6] 就是三段区间的右端坐标。把整条数轴想成 1 到 6 的 6 个整数点，每个点落在哪段、就选那个下标——点越多的段(权重越大)越容易中。

每次抽样：先掷一个 1~6 的随机数 target，然后在有序的 pre 里二分找第一个 ≥ target 的位置——这就是 target 这个点落进的区间下标。下面拿 target=4 演一遍二分。

抽样 · 掷出 target=4：假设这次随机掷出 target=4。它落在数轴的哪一段？用二分在 pre=[1,4,6] 上找第一个 ≥ 4 的格子。

二分开局：二分找下界：lo 指 0、hi 指 3（= n，数组外一格）。答案下标就夹在 [lo, hi) 之间，慢慢往中间收。

第 1 轮 · mid 落点：mid 落在下标 1。看 pre[mid]=pre[1]=4 与 target=4 比一比，决定往哪边收。

第 1 轮 · 比较 pre[mid] 与 target：pre[1]=4 ≥ target=4，说明下标 1 够大、可能就是答案，但还要看左边有没有更小的也满足，所以 hi=mid=1(保留 mid 自己，故不是 mid−1)。

第 1 轮 · 收缩到 [0,1)：hi 收到 1，下标 2 变灰出局——它的右端 6 比 4 大没错，但更靠右、不会是第一个满足的。范围缩成 [0,1)。

第 2 轮 · mid 落点：新范围 [0,1) 里取中点，mid 落到下标 0。再比一次 pre[0] 和 target。

第 2 轮 · 比较 pre[mid] 与 target：pre[0]=1 < target=4，下标 0 的区间右端才到 1，装不下 target=4。它出局(变灰)，lo=mid+1=1。

二分结束 · lo=hi=1：lo 和 hi 撞到一起停下，命中下标 1。target=4 确实落在区间 (1,4] 里——pickIndex() 这次返回 1。

命中验证：复核一眼：4 比 pre[0]=1 大、又 ≤ pre[1]=4，正好卡在下标 1 的区间 (1,4] 里。返回 1 无误。

再抽一次 · 掷出 target=5：换个随机数 target=5 再演一遍，体会二分每次怎么收。lo=0, hi=3 重新开局。

target=5 · 第 1 轮 mid：mid 落下标 1，pre[1]=4 < target=5，下标 1 的区间右端才到 4、装不下 5。下标 1 出局，lo 跳到 2。

target=5 · 第 2 轮 mid：范围缩到 [2,3)，mid 落下标 2，pre[2]=6 ≥ 5，下标 2 够大，hi 收到 2。

target=5 · 命中下标 2：lo、hi 撞在下标 2 停下，命中下标 2。target=5 落在区间 (4,6]，返回 2。

换个点 · target=1 落哪：再掷一个 target=1：第一个 ≥ 1 的是 pre[0]=1，命中下标 0。6 个点里只有 1 落进 0 的区间——所以下标 0 概率 1/6，和权重对上。

换个点 · target=6 落哪：再掷 target=6：第一个 ≥ 6 的是 pre[2]=6，命中下标 2。点 5、6 都落进 2 的区间(长度 2)，概率 2/6——区间越长越容易中，正是按权重。

概率核对 · 6 个点的归属：把 1~6 全掷一遍：1 个点归下标 0、3 个点归下标 1、2 个点归下标 2，比例 1:3:2 正好是权重比。前缀和把权重变成了区间长度，二分让每次抽样只花 O(log n)。

边界三连：三种极端：单元素必返回它、权重 0 的下标被天然跳过、边界点归左不归右——「第一个 ≥」全兜住。

「带权随机」「按频率采样」这类问题都能往这个模板靠：前缀和把离散权重摊成连续数轴，二分把一次采样压到对数级。是离线采样的经典套路。

面试追问：把「为何前缀和+二分而非摊开」「二分对象是前缀和、找下界」讲透，是这题的面试加分项。