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
What would be an estimate of N : 10^3, 10^6, 10^9 ?