loicfevrier

3 ms·

1. 1.▲
   by loicfevrier 18y ago

   Which language are you using ? Matlab, C/C++ ? What would be an estimate of N : 10^3, 10^6, 10^9 ?
2. 2.▲
   by loicfevrier 18y ago

   Exact, I forgot that point.
3. 3.▲
   by loicfevrier 18y ago

   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).
4. 4.▲
   by loicfevrier 18y ago

   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
5. 5.▲
   by loicfevrier 18y ago

   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&#3...