Um array de somas de prefixos responde totais de intervalo em O(1), mas um único valor alterado obriga você a refazer O(n) entradas dele. Uma árvore de Fenwick, também chamada de árvore indexada binária, troca um pouco da velocidade das consultas por atualizações rápidas: as duas operações custam O(log n).
A ideia cabe em dois loops. A célula tree[i] guarda o total dos últimos i & -i valores que terminam na posição i, onde i & -i é o bit ativo mais baixo de i. Para somar na posição i, suba com i += i & -i, tocando cada célula que a cobre. Para ler o prefixo até i, desça com i -= i & -i, somando células disjuntas. A árvore começa no índice 1 porque o 0 não tem bit ativo mais baixo.
Recorra a uma árvore de Fenwick quando os valores mudam entre perguntas de prefixo ou de soma de intervalo, ou quando você conta coisas "até agora" por valor: pontuações anteriores abaixo desta, ou timestamps anteriores acima dela. Combinada com um array de diferenças, ela também resolve atualizações de intervalo com consultas pontuais. Para mínimos, máximos ou combinações mais complexas, use uma árvore de segmentos.
As atualizações sobem pelo bit ativo mais baixo; as leituras de prefixo descem por ele.