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?
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.