Uma soma de prefixos guarda totais acumulados para que o total de qualquer intervalo se reduza a uma subtração. Se prefix[i] é o total dos primeiros i valores, o intervalo de left a right vale prefix[right + 1] - prefix[left]. O zero extra no início permite que um intervalo comece no índice 0 sem tratá-lo como caso especial.
Recorra às somas de prefixos quando um problema faz muitas perguntas de intervalo sobre dados que não mudam, ou quando pede para contar os intervalos que somam um determinado valor. Para contar intervalos, elas se combinam com um mapa hash: um intervalo que termina aqui soma o alvo quando algum prefixo anterior vale o total atual menos o alvo. Isso funciona com números negativos, onde uma janela deslizante não sabe quando encolher.
Um array de diferenças aplica a ideia ao contrário. Em vez de guardar valores, guarde onde cada mudança começa e onde termina, e calcule uma soma acumulada no final. O mesmo truque da subtração se estende a grades: uma tabela de prefixos 2D dá o total de qualquer retângulo com quatro consultas.
O total de um intervalo é a diferença entre duas somas de prefixos.