Sommes préfixes et totaux cumulés

Étant donné un tableau nums, vous devez répondre à de nombreuses requêtes de la forme suivante : quelle est la somme des éléments de l’indice i à l’indice j ? Calculer chaque requête naïvement prend O(n), si bien que k requêtes coûtent O(n×k). Avec un tableau de sommes préfixes, vous précalculez un total cumulé en O(n), puis répondez à chaque requête en O(1). Il s’agit de l’une des techniques de précalcul les plus utilisées lors des entretiens.

Définissez prefix[i] comme la somme de nums[0] à nums[i-1] (une case supplémentaire et un décalage d’un indice, avec un tableau indexé à partir de zéro, simplifient les cas limites). Construisez-le en O(n) en un seul parcours : prefix[i] = prefix[i-1] + nums[i-1]. Une requête sur l’intervalle sum(i, j) devient alors prefix[j+1] - prefix[i] : une seule soustraction coûtant O(1).

Trouver le nombre de sous-tableaux dont la somme est égale à k est un problème classique combinant table de hachage et somme préfixe. L’idée clé est la suivante : la somme du sous-tableau allant de i à j vaut prefix[j] - prefix[i-1]. Si nous voulons qu’elle soit égale à k, alors prefix[i-1] = prefix[j] - k. En parcourant le tableau de gauche à droite tout en maintenant une somme préfixe cumulée, nous recherchons combien de fois current_sum - k est déjà apparu, ce qui permet de compter tous les sous-tableaux valides en O(n) au total.

La somme maximale d’un sous-tableau peut être formulée comme un problème de somme préfixe : pour chaque indice j, nous voulons maximiser prefix[j] - prefix[i] pour tout i < j. À chaque indice j, le i optimal est celui qui correspond à la plus petite somme préfixe observée jusque-là. Un parcours de gauche à droite en mémorisant min_prefix donne une complexité O(n). Cela revient à voir l’algorithme de Kadane sous l’angle des sommes préfixes.

Les sommes préfixes s’étendent aux grilles 2D. Définissez P[i][j] comme la somme de tous les éléments du rectangle allant de (0,0) à (i-1,j-1). Construisez-le avec la formule d’inclusion-exclusion : P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + grid[i-1][j-1]. Toute requête de somme du rectangle allant de (r1,c1) à (r2,c2) peut alors être traitée en O(1) à l’aide de quatre consultations.

L’indice d’équilibre est la position où la somme des éléments à gauche est égale à la somme des éléments à droite. Précalculez la somme totale, puis parcourez le tableau en maintenant une somme cumulée à gauche. La somme à droite vaut total - left_sum - nums[i]. Vérifiez l’égalité en O(1) pour chaque indice, soit O(n) au total. Cela montre comment un total cumulé peut remplacer deux tableaux de sommes préfixes distincts.

Étant donné un tableau, renvoyez un tableau où chaque élément est le produit de tous les autres. La division est interdite. Utilisez un produit préfixe et un produit suffixe : résultat[i] = (produit de tous les éléments avant i) × (produit de tous les éléments après i). Construisez les produits préfixes lors d’un parcours de gauche à droite, puis multipliez-les par les produits suffixes lors d’un parcours de droite à gauche en utilisant une variable cumulée — aucun tableau supplémentaire n’est nécessaire pour les suffixes.

Certains problèmes demandent le nombre de sous-tableaux dont la somme est divisible par k. En utilisant les sommes préfixes modulo k, si prefix[j] % k == prefix[i] % k, alors sum(i+1..j) est divisible par k. Une table de hachage qui compte chaque valeur de reste au fur et à mesure du parcours donne une complexité O(n). L’initialisation essentielle est freq[0] = 1 pour prendre en compte les sous-tableaux commençant à l’indice 0.

Un tableau des différences est l’inverse d’une somme préfixe. Étant donné un tableau, précalculez diff[i] = nums[i] - nums[i-1]. Ajouter x à un intervalle [l, r] ne nécessite que deux opérations O(1) sur le tableau des différences : diff[l] += x et diff[r+1] -= x. Après toutes les mises à jour, reconstruisez le tableau de résultat en un seul parcours de somme préfixe. Cela transforme k mises à jour d’intervalles, de O(n×k) en O(n + k).

Les sommes préfixes apparaissent dans de nombreuses catégories de problèmes :

• Requêtes sur des intervalles — somme d’un sous-tableau, somme d’un rectangle
• Comptage de sous-tableaux — somme égale à k, divisible par k
• Problèmes de produits — produit de tous les éléments sauf soi-même
• Équilibre — trouver l’indice d’équilibre
• Mises à jour d’intervalles — tableau des différences

Au-delà des sommes préfixes, de nombreux problèmes utilisent un maximum cumulé ou un minimum cumulé conservé dans une seule variable. Le problème du meilleur moment pour acheter et vendre des actions utilise un prix minimal cumulé ; le calcul de l’eau de pluie piégée depuis la gauche utilise une hauteur maximale cumulée à gauche. Ces schémas ne nécessitent qu’un seul parcours et O(1) espace supplémentaire, ce qui en fait la référence absolue en matière d’efficacité temporelle et spatiale.

Vérifiez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation — présentés dans cette leçon.

Dans cette leçon, vous avez appris que les sommes préfixes transforment les requêtes sur des intervalles en O(n) en consultations O(1) grâce au précalcul des sommes cumulées lors d’un seul parcours en O(n), que la combinaison des sommes préfixes et d’une table de hachage permet des solutions en O(n) pour compter les sous-tableaux ayant une somme donnée ou une propriété de divisibilité donnée, et que les tableaux des différences sont l’inverse : ils permettent d’effectuer des mises à jour d’intervalles en O(1), puis de reconstruire le résultat en un seul parcours de somme préfixe à la fin. Nous allons maintenant aborder la technique des deux pointeurs, en commençant par les pointeurs placés aux extrémités opposées.