05 — Les sommes préfixes

Ce que tu vas apprendre

• Le principe des sommes préfixes et le précalcul
• Répondre à une requête de somme sur une plage en O(1)
• L'extension aux tableaux 2D
• Quand préférer les sommes préfixes à la fenêtre glissante

Prérequis

• 04 — La fenêtre glissante

Les sommes préfixes répondent à un besoin précis : tu as un tableau fixe et tu dois répondre à beaucoup de questions du type « quelle est la somme entre les index i et j ? ». Recalculer chaque somme coûterait O(n) par requête. Avec un précalcul en O(n) fait une seule fois, chaque requête devient O(1). C'est l'application directe du compromis temps/espace : on investit de la mémoire et un calcul initial pour amortir des milliers de requêtes.

Le principe

Une somme préfixe prefixe[i] contient la somme de tous les éléments du tableau jusqu'à l'index i exclu. On la construit en une passe.

pythondef construire_prefixes(arr: list[int]) -> list[int]:
    prefixe = [0] * (len(arr) + 1)   # prefixe[0] = 0
    for i, x in enumerate(arr):
        prefixe[i + 1] = prefixe[i] + x
    return prefixe

Pour arr = [3, 1, 4, 1, 5], on obtient prefixe = [0, 3, 4, 8, 9, 14]. La case supplémentaire au début (la somme vide à 0) simplifie les calculs et évite les cas particuliers.

La requête en O(1)

La somme des éléments entre les index i et j inclus est la différence de deux sommes préfixes : tout ce qui va jusqu'à j, moins tout ce qui va jusqu'avant i.

pythondef somme_plage(prefixe: list[int], i: int, j: int) -> int:
    return prefixe[j + 1] - prefixe[i]

Pour la somme entre les index 1 et 3 de [3, 1, 4, 1, 5], soit 1 + 4 + 1 = 6 : prefixe[4] - prefixe[1] = 9 - 3 = 6. Une soustraction, peu importe la taille de la plage. C'est O(1).

Le bilan : construction O(n) une fois, puis chaque requête en O(1). Pour q requêtes, on passe de O(q × n) à O(n + q). Dès qu'il y a plusieurs requêtes, c'est gagnant.

typescriptclass SommePrefixe {
  private prefixe: number[];
  constructor(arr: number[]) {
    this.prefixe = [0];
    for (const x of arr) {
      this.prefixe.push(this.prefixe[this.prefixe.length - 1] + x);
    }
  }
  // somme inclusive de i à j
  plage(i: number, j: number): number {
    return this.prefixe[j + 1] - this.prefixe[i];
  }
}

L'extension en 2D

Le pattern se généralise aux matrices, pour répondre à « quelle est la somme du rectangle entre (r1, c1) et (r2, c2) ? ». On précalcule une matrice de sommes préfixes 2D, où chaque case contient la somme du rectangle depuis l'origine. Une requête combine alors quatre valeurs par inclusion-exclusion.

python# somme du rectangle (r1,c1)-(r2,c2), après précalcul de P
def somme_rectangle(P, r1, c1, r2, c2):
    return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

Le précalcul est O(lignes × colonnes), et chaque requête de rectangle est O(1). C'est utilisé en traitement d'image (somme de zones) et dans les tables de sommes intégrales.

Sommes préfixes ou fenêtre glissante ?

Les deux patterns évitent le recalcul, mais répondent à des besoins différents.

• La fenêtre glissante convient quand on cherche un sous-tableau optimal en une seule passe, en faisant glisser une fenêtre. Le tableau peut même être un flux qu'on lit une fois.
• Les sommes préfixes conviennent quand le tableau est fixe et qu'on doit répondre à de nombreuses requêtes de plages arbitraires, dans n'importe quel ordre.

Une limite à connaître : les sommes préfixes supposent que le tableau ne change pas. Si les valeurs sont modifiées entre les requêtes, il faut reconstruire les préfixes (O(n) à chaque modification). Pour un tableau qui évolue avec des requêtes de somme fréquentes, on utilise une structure plus avancée, l'arbre de Fenwick (Binary Indexed Tree), qui gère mise à jour et requête en O(log n) chacune. C'est hors du cadre de cette série, mais c'est la suite logique quand les sommes préfixes ne suffisent plus.

L'article suivant clôt la série en synthétisant : face à un problème de tableau, comment reconnaître lequel des quatre patterns appliquer.

Sources

• Halim, S., & Halim, F. (2013). Competitive Programming 3, Section 3.5 et 9.x (sommes préfixes 1D/2D, Fenwick). Lulu.
• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Fenwick, P. M. (1994). A New Data Structure for Cumulative Frequency Tables. Software: Practice and Experience, 24(3). (Pour aller plus loin que les préfixes statiques)