O que é uma soma de prefixo e como ela acelera consultas de intervalo?

Question

Accepted Answer

Um array de **prefix sum** armazena totais cumulativos para que qualquer **range sum** possa ser respondida em **O(1)** após O(n) de pré-processamento — em vez de O(n) por consulta.

## A ideia

Seja `prefix[i]` a soma dos primeiros `i` elementos. Então a soma de `arr[l..r]` é `prefix[r+1] - prefix[l]`.

## Exemplo

```python
def build_prefix(arr):
    prefix = [0] * (len(arr) + 1)
    for i, x in enumerate(arr):
        prefix[i + 1] = prefix[i] + x   # running total
    return prefix

def range_sum(prefix, l, r):            # inclusive l..r
    return prefix[r + 1] - prefix[l]    # O(1)

p = build_prefix([2, 4, 1, 3, 5])
range_sum(p, 1, 3)                      # 4+1+3 -> 8
```

## Rastreamento

```text
arr    = [2, 4, 1, 3, 5]
prefix = [0, 2, 6, 7, 10, 15]
sum(1..3) = prefix[4] - prefix[1] = 10 - 2 = 8
```

## Complexidade

- **Construção:** O(n). **Consulta:** O(1). **Espaço:** O(n).

## Quando usar / armadilhas

Ideal para **muitas consultas de range-sum** em dados estáticos. Variantes: somas de prefixo 2D para somas de submatrizes, XOR de prefixo e arrays de diferenças para atualizações de intervalo. Se o array muda frequentemente, use uma árvore Fenwick/segment. Cuidado com o deslocamento de índice (tamanho n+1).

## Por que isso importa

Somas de prefixo transformam consultas de intervalo O(n) repetidas em buscas O(1) — uma vitória enorme quando as consultas são frequentes.

O padrão de pré-calcular uma vez e responder rápido generaliza para muitas tarefas de processamento de dados.

É um elemento essencial da programação competitiva e um bloco de construção comum em análise.