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