累積和配列なら範囲の合計にO(1)で答えられますが、値が1つ変わるだけでO(n)分を作り直す必要があります。フェニック木はBinary Indexed Treeとも呼ばれ、クエリの速さを少し犠牲にして更新を速くします:どちらもO(log n)です。
この考え方は2つのループに収まります。セルtree[i]は、位置iで終わる直近のi & -i個の値の合計を格納し、i & -iはiの最下位の立っているビットです。位置iに加算するには、i += i & -iで上へ進み、そこをカバーするすべてのセルを更新します。iまでの累積和を読むには、i -= i & -iで下へ進み、重ならないセルを足していきます。0には最下位の立っているビットがないので、木は1始まりのインデックスです。
累積和や範囲の合計を問い合わせる合間に値が変わるとき、または値ごとに「ここまで」の個数を数えるとき(この値より低い以前のスコアや、この値より大きい以前のタイムスタンプなど)は、フェニック木を使います。差分配列と組み合わせれば、範囲更新と一点照会にも対応できます。最小値、最大値、もっと複雑な結合には、代わりにセグメント木を使ってください。