权重随机取值题followup 权重可变 算法题求解

利口上的无儿吧， 是道比较高频的题目。 面经里面经常看到各种马甲，原题的思路基本都是计算前缀和， 然后放入treemap为key， value是id。 这个思路应该没问题。

但是经常看到followup，要求权重可变。马甲基本就是说什么随机拿不同颜色的球（颜色是id，球个数是weight）。 要求拿出来不能放回，或者可以加球。 这样weight就会变。 这时候怎么处理。

这种前缀和可变的情况，比较常见的思路就是想到BIT或者线段树。 这题感觉BIT应该更合适一点。 可是问题是这题更新权重之后， 我的理解是必须还是要有全部的preSum才能随机取值。 虽然BIT更新bit array是logN。但是计算新的全部的presum还是O(N)。 那这样看来也没能降低TC啊？  我想了半天也没想到什么太好的办法，是不是我对BIT的理解不对， 或者整个思路就不对？

希望大佬们指点一下。

wisdompeak2 发表于 2021-3-30 02:12
我感觉你对这棵树存放的东西是什么并没有正确的理解。
root节点的val存放的就是全部的权重和。其他节点 ...

恩，同意。 我是搜索的方式想歪了，根据你的提示我大概写了下搜索的代码：

输入的root就是segment tree的根。 random就是随机生成的数，返回找到的id。
query(start, end) 就是query segment tree。

1. int getId(root, int random)
   
2. {
   
3. int left = root.start;
   
4. int right = root.end;
   
5. int mid = 0;
   
6. while(left < right)
   
7. {
   
8.   mid = left + (right - left) /2
   
9.   int preSum = query(left, mid);
   
10.   if preSum == random
    
11.    return mid;
    
12.   if preSum > random
    
13.    right = id-1;
    
14.   else
    
15.    left = id;
    
16.    random -= presum;
    
17. }
    
18. return left;
    
19. }
    

复制代码

最后的TC= logN * logN。

大概就是这个思路吧？

wisdompeak2 发表于 2021-3-29 10:06
用线段树的好处是不需要显示地更新所有前缀和，只需要更新有必要更新的前缀和。
线段树单点更新是log(N)。 ...

恩，我仔细想想的确线段树比较合适。 因为前缀和数组， 数组长度不变，只是一部分前缀和变化，那么线段树应该就可以用。

对于线段树，start和end存数组的index。 对于非叶node， 值存什么呢？ 我觉得应该是start和end中间index所对应在前缀和数组里面的值。
假设前缀和数组如下：
presum = [0, 100, 200, 300, 400, 500]

所以对于根节点:
start = 0,
end = 5,
val = presum[(start + end)/2] = 200.

是不是应该这样建树？
但是更新前缀和， 虽然单点更新是logN。 可以现实情况更新基本不可能是单点更新， 比如上面的例子，对于index=1 加1， 那么index 1到5都要更新。 这种多点更新，线段树的复杂度是多少？ 肯定低于nlogn （否则岂不是比直接用presum数组更慢了。。。），因为更新过程中有很多重复。

这个问题在Weighted random sampling with a reservoir中提出了一个非常巧妙的方法，不过文章不是open access.. 参考这里的简单描述：
https://utopia.duth.gr/~pefraimi/research/data/2007EncOfAlg.pdf

算法是这样的，给定一组weight w(1), ..., w(n)，首先生成n个在(0,1)区间内均匀分布的随机值X(1), ..., X(n)

定义 m(i) = X(i) ^ (1 / w(i))，那么第k次拿的球就是{ j | m(j) 在m[1..n]中是第k大的值 }

证明要用到概率计算方面一些比较巧妙的性质，因为不是open access我也看不到..

同一个作者另外一篇相关文章：Weighted Random Sampling over Data Streams
https://arxiv.org/pdf/1012.0256.pdf

用线段树的好处是不需要显示地更新所有前缀和，只需要更新有必要更新的前缀和。
线段树单点更新是log(N)。
更新完线段树之后，如果get一个随机数，想知道它是落在哪个前缀区间，我觉得只能用二分搜索（即看是不是前10个区间的前缀，前5个区间的前缀、），这样的搜索本身是log(N)。另外query一个前缀区间的区间和也是log(N)。所以时间复杂度是2logN，是不是有点优势？

叶子节点存放的难道不是每个球的权重吗？非叶子节点存放的是对应区间的权重和。
每次你想求前k个球的权重和（即前缀和），那么就是queryRangeSum(0, k).

你用BIT更新了bit那个array就行了啊，这个复杂度是logn，之后你可以直接二分啊，每次到了哪里再query前缀和，每次query复杂度是logn，总共logn次query，复杂度也不过就是logn*logn而已。如果线段树的话，update是logn，最后查询也是logn，因为每次只能往左或者往右，复杂度就是树的高度。

内存足够大的话，multiset试试。

wisdompeak2 发表于 2021-3-29 11:15
叶子节点存放的难道不是每个球的权重吗？非叶子节点存放的是对应区间的权重和。
每次你想求前k个球的权重 ...

"非叶子节点存放的是对应区间的权重和"

比如我那个例子，那么root节点的val就是1500. 比如query的输入是1000， 怎么知道往左走还是往右走？ 先检查左子节点的val然后判断？

不知道小帅 发表于 2021-3-29 12:33
你用BIT更新了bit那个array就行了啊，这个复杂度是logn，之后你可以直接二分啊，每次到了哪里再query前缀和 ...

我对BIT的理解可能不够。 请问如果更新了bit数组之后， presum没有更新。那这个时候进来一个值，要二分查找它对应的presum的index，应该怎么做？ 如何二分？

多谢。

bigboss789 发表于 2021-3-29 21:16
我对BIT的理解可能不够。 请问如果更新了bit数组之后， presum没有更新。那这个时候进来一个值，要二分查 ...

主要是因为权重都是非负的，所以进来一个值，你就先查mid看看是不是小于这个值，query到mid的时间是log级别的。然后你根据和mid的大小比较往左还是往右。总共只需要查logn次，每次查询是log的复杂度。