Qu'est-ce qu'une somme de préfixe et comment accélère-t-elle les requêtes de plage ?

Question

Accepted Answer

Un tableau de **somme de préfixe** stocke les totaux cumulatifs afin que toute **somme de plage** puisse être répondue en **O(1)** après un prétraitement O(n) — au lieu de O(n) par requête.

## L'idée

Soit `prefix[i]` la somme des `i` premiers éléments. Alors la somme de `arr[l..r]` est `prefix[r+1] - prefix[l]`.

## Exemple

```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
```

## Trace

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

## Complexité

- **Construction :** O(n). **Requête :** O(1). **Espace :** O(n).

## Quand l'utiliser / pièges

Idéale pour **nombreuses requêtes de somme de plage** sur données statiques. Variantes : sommes de préfixe 2D pour sommes de sous-matrice, XOR de préfixe, et tableaux de différence pour mises à jour de plage. Si le tableau change souvent, utilisez plutôt un arbre de Fenwick/segment. Attention au décalage d'index (taille n+1).

## Pourquoi c'est important

Les sommes de préfixe transforment des requêtes de plage O(n) répétées en des recherches O(1) — un énorme gain lorsque les requêtes sont fréquentes.

Le modèle précontrôler une fois, répondre rapidement se généralise à de nombreuses tâches de traitement de données.

C'est un élément essentiel de la programmation compétitive et un bloc de construction courant en analyse.