News for hackers. Stuff that matters.
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...
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.