Additionner n’importe quelle plage par soustraction

La construction du tableau de sommes préfixes n’était que la préparation. Voici maintenant la magie : répondre à toute somme d’intervalle avec une seule soustraction. ⚡

Une somme d’intervalle est simplement un grand total moins un total plus petit. Soustraire deux valeurs de sommes préfixes annule proprement tout ce qui se trouve en dehors de votre intervalle.

Pour additionner les éléments de l à r, prenez prefix[r + 1] moins prefix[l]. Cette unique formule fonctionne pour tout intervalle.

prefix[r + 1] contient tout jusqu'à r, tandis que prefix[l] contient tout ce qui précède l. La différence laisse exactement la portion centrale.

Pour [3, 1, 4], le préfixe est [0, 3, 4, 8]. Pour additionner les indices 1 à 2, calculez 8 moins 3, ce qui donne 5. Cela correspond bien à 1 plus 4.

Chaque requête consiste simplement en une soustraction, donc elle s'exécute en O(1). Mille requêtes coûtent autant par requête qu'une seule.

L'erreur la plus courante concerne l'indice de la borne supérieure. Avec un zéro initial, utilisez toujours prefix[r + 1], et non prefix[r]. Vérifiez cette limite.

Décidez dès le début si r est inclus. Cette formule considère l'intervalle comme inclusif de l et de r, ce qu'attendent la plupart des problèmes de concours.

Une petite fonction auxiliaire rend votre logique plus lisible et regroupe vos indices au même endroit. Appuyez-vous sur cette fonction auxiliaire plutôt que d'intégrer les calculs directement.

Pour additionner le tableau entier, utilisez l égal à 0 et r égal à n moins 1. La formule donne prefix[n], le total général.

Chaque fois qu'un problème pose de nombreuses questions de somme sur un intervalle d'un tableau fixe, les sommes préfixes transforment une boucle en O(n) par requête en réponses instantanées.

Vous pouvez maintenant calculer toute somme sur un intervalle en O(1) avec prefix[r + 1] moins prefix[l]. Faites attention au décalage dû au zéro initial et vous éviterez les bogues. ✅