title: Insert element at position i and return info based on i first elements
body: <p>Let's say I have a list of integers:</p>
  
  <pre><code>2, 1, 3, 1, 4, 2, 5, 3, 2
  </code></pre>
  
  <p>I want to be able to insert a new integer at position <code>i</code>. So let's say <code>i</code> is 4, and I want to insert the number 7. The result would be:</p>
  
  <pre><code>2, 1, 3, 7, 1, 4, 2, 5, 3, 2
  </code></pre>
  
  <p>After the insertion, I would like to receive some information based on numbers at positions <code>i</code> and lower. For example, the sum of the first <code>i</code> numbers. In this case it would be <code>2 + 1 + 3 + 7 = 13</code>.</p>
  
  <p>I want to be able to repeat this process over and over.</p>
  
  <p>I wrote a program in C++ that uses <code>std::list</code>. Here's what it does to insert <code>n</code> at position <code>i</code> into <code>List</code> and then return the sum of <code>i</code> first numbers:</p>
  
  <ol>
  <li>Compare the last insert position <code>k</code> with <code>i</code>. If it's lower, calculate <code>sum[j]</code> for each <code>j: k &lt; j &lt; i</code> like this: <code>sum[j] = sum[j-1] + List[j]</code> <em>- O(n)</em></li>
  <li>Find position <code>i</code> <em>- O(n)</em></li>
  <li>Insert <code>n</code> at position <code>i</code>, store <code>k = i</code> <em>- O(1)</em></li>
  <li>Calculate and return <code>sum[i] = sum[i-1] + n</code> <em>- O(1)</em></li>
  </ol>
  
  <p>Can this be done more efficiently, perhaps using a different data structure? In <em>O(logn)</em> maybe? If yes then how?</p>