# Efficient dynamic summation of list of numbers?

Keeping count of the sum of a list ($S_0$) of $k$ numbers in an auxillary structure $S_1$.

### Example contents

$S_0 = [5,9,2,5,3,6,7]$

$S_1 = [14, 16, 21, 24, 30, 37]$

Where the formula for $S_1$ is: $S_1[0]=S_0[0]+S_0[1],\ S_1[1]=S_1[0]+S_0[2], S_1[2]= \cdots$

Given a modification of $\pm 1$ to any element in $S_0$, is there a method of recalculating $S_1$ in less than $\mathcal{O}(k)$ worst-case?

-
If it is needed to reduce complexity; a third auxiliary structure $S_2$ can also be introduced holding the reverse sum; i.e.: $S_2=[S_0[k-1]+S_0[k-2], S_1[0]+S_0[k-3] +\cdots$] –  A T Jan 27 '13 at 8:06

Binary index trees (aka Fenwick trees) allow the construction of $S_1$ in $O(n \log n)$, queries in $S_1$ in $O(\log n)$ and updates to $S_0$ (incrementing or decrementing any value by an arbitrary amount) in $O(\log n)$. All in $O(n)$ space.