title: What is a good datastructure to keep cumulative values in?
body: <p>I am looking for an idea, concept or proven datastructure that would be very efficient when accessing a collection that keeps cumulative values. </p>
  
  <p>Example may shed more light on my need:</p>
  
  <p>I have a list of values (2,3,5).
  This list when looking at the cumulative values would be (2,5,10).</p>
  
  <p>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).</p>
  
  <p>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.</p>
  
  <p>Any ideas or hints ?</p>
  
  <p>@Kristo (too long to put in the commentary): To clarify why negative numbers would make the total sum value meaningless please follow this example.</p>
  
  <p>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)</p>
  
  <p>If my "magic number" were 4 total sum wouldn't tell me whether I've exceeded it.</p>
  
  <p>PS: The main reason for this is to be able to tell if I went over a certain value and where in the chain.</p>