3 ms·
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.
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&d2=binaryIndexedTrees http://www.topcoder.com/tc?module=Static&d1=tutorials...
- bravura 18y agoIt appears that Binary Indexed Trees are appropriate only when the weights are integral?
- loicfevrier 18y agoExact, I forgot that point.