What is a good datastructure to keep cumulative values in?

Question

I am looking for an idea, concept or proven datastructure that would be very efficient when accessing a collection that keeps cumulative values.

Example may shed more light on my need:

I have a list of values (2,3,5). This list when looking at the cumulative values would be (2,5,10).

I will now add 1 at the start of the list and get (1,2,3,5) and in cumulative terms (1,3,6,11).

I only need to look at the cumulative values, I am not at all interested in the 1,2,3,5. I need to be able to quickly insert at position, remove a position and all this should quickly update the cumulative array (ideally without iterating throughout the whole array and recalculating the values.

Any ideas or hints ?

@Kristo (too long to put in the commentary): To clarify why negative numbers would make the total sum value meaningless please follow this example.

Insert 1 followed by -1. Sum is 1 than 0. (1,-1) // (1,0) Insert 3 followed by insert -3. Sum is 3 then 0. (1,3,-1,-3) // (1,4,3,0) Insert 2 followed by insert -2. Sum is 2 then 0. (1,3,2,-1,-2,-3) // (1,4,6,5,3,0)

If my "magic number" were 4 total sum wouldn't tell me whether I've exceeded it.

PS: The main reason for this is to be able to tell if I went over a certain value and where in the chain.

Answer 1

The only optimization I can think of is to do a 'lazy' evaluation of the cumulative list.

in addition to your list of source values, keep track of a number of the highest position in the cumulative list that is accurate. if you need a number higher than that then you walk up the list, updating the values, and the index.

idx  values       cumulative    operation
 3   (2,3,5)      (2, 5, 10)
 0   (1,2,3,5)    (X,X,X,X)     insert 1 at 0 
 3   (1,2,3,5)    (1,3,6,X)     look for value over 5     
 3   (1,2,3,5,4)  (1,3,6,X,X)   insert 4 at 4 

if course, this wont do you a whole lot of good if you are usually adding items early in the list....

Answer 2

Check the cumulative frequency table.