loicfevrier

Which language are you using ? Matlab, C/C++ ?

What would be an estimate of N : 10^3, 10^6, 10^9 ?

Exact, I forgot that point.

It means that K is much smaller that N. Because if K is a O(N) then doing an update in O(log n) is not good, it is better to rebuild the whole strcuture in O(n).

Red-black trees are far too complex for this simple task : just use any binary balanced tree so that the maximum height is O(log n). (red-black trees will work but take any one you want, red-black tree are slow) On each node you store two numbers : - sum of the weights at the left - sum of the weights at the right Want you want to choose an item just explore the tree and for each node choose left or right according to the two weights. ==> O(log n) If you update an item you'll need to update all the weight up to the root of the tree. ==> O(log n) for each update

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...