title: What do we call a dynamic programic construct that allows us to compute sums of any range in logarithmic time?
body: <p>I was usually calling it ‘partial sums’, but I dunno how is it ‘officially’ called, and I have the impression it is not ‘partial sums’.</p>
  
  <p>Anyway, the concept is pretty simple. Say you have an array of <code>8</code> elements, <code>[3, 7, 2, 1, 5, 6, 9, 4]</code>. You compute sums like that:</p>
  
  <p><a href="https://i.stack.imgur.com/udpPN.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/udpPN.png" alt="enter image description here"></a></p>
  
  <p>Of course, this will lead to an array of arrays of this form:</p>
  
  <p><a href="https://i.stack.imgur.com/rc51h.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/rc51h.png" alt="enter image description here"></a></p>
  
  <p>Now if we are asked, for example, what is the sum of elements of indexes from <code>0</code> till <code>4</code> we won’t linearily calculate that sum, but instead we will know it is equal to the sum of elements from <code>0</code> till <code>3</code> (which is <code>13</code>) and then logarithmically go down till the element <code>5</code>. So, the answer is: <code>18</code>.</p>
  
  <p>How should I call such a construct so that other peaople know what I’m talking about without drawing tables like these?</p>