Re:Ask HN: Fast sampling and update of weighted items? (data...
by loicfevrier on Wednesday March 25, 2009 @03:29PM
(#532296)
But you will need to re-compute the sum each time you are doing an update wich takes O(n).
You can use Binary Indexed Trees to do that efficiently : http://www.topcoder.com/tc?module=Static&d1=tutorials...
[ Parent
| on HN ]
Re:Ask HN: Fast sampling and update of weighted items? (data...
by bravura on Wednesday March 25, 2009 @04:25PM
(#532375)
It appears that Binary Indexed Trees are appropriate only when the weights are integral?
Re:Ask HN: Fast sampling and update of weighted items? (data...
by loicfevrier on Wednesday March 25, 2009 @04:44PM
(#532401)
Exact, I forgot that point.