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

bigboss789 发表于 2021-3-29 21:12
"非叶子节点存放的是对应区间的权重和"

比如我那个例子，那么root节点的val就是1500. 比如query的输入 ...

我感觉你对这棵树存放的东西是什么并没有正确的理解。
root节点的val存放的就是全部的权重和。其他节点的val存放的是对应区间的权重和。
query的输入的参数是一段区间，比如说query[0,5]，表示从线段树里读取前5个球的权重和。
二分搜索的是输入的参数，试图找到一个前缀和恰好大于生成的随机数。比如说如果[0,6]恰好大于生成的随机数，那么说明这个随机数对应的是第6号球。

楼上两位老哥貌似说的是对的，binary search + segment tree / binary index tree. 楼主貌似纠结在了presume上了，他们的实现方式里是不需要构建presume数组的， 比如说segment tree本身就可以拿到任意区间，这样结合binary search(这个binary search不是在presume上找，不是用c++的lower_bond或者python的bisect_left，而是自己另写一段binary search)，总体时间O(logn*logn)，就可以找到目标位置了。

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。

大概就是这个思路吧？

没怎么细想，但感觉不太对劲。我改了一下。

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(0, mid);
   
10.   if preSum >= random
    
11.    right = mid;
    
12.   else
    
13.    left = mid+1;
    
14.  }
    
15.  return left;
    
16. }

复制代码

wisdompeak2 发表于 2021-3-30 04:37
没怎么细想，但感觉不太对劲。我改了一下。

[mw_shl_code=java,true]int getId(root, int random)

多谢， 学习了。

你的写法应该是比较常见的。不过我觉得我的也是对的，哈哈

magicsets 发表于 2021-3-29 13:53
这个问题在Weighted random sampling with a reservoir中提出了一个非常巧妙的方法，不过文章不是open acce ...

如果max weight 是bounded的话，是有on average O(1) 的方法的。