Introduction aux sommes préfixes
La technique des sommes préfixes permet de répondre efficacement aux requêtes de somme sur un intervalle. Elle consiste à précalculer un tableau intermédiaire en O(N) pour ensuite répondre à chaque requête [l, r] en O(1) grâce à la formule : somme[r] - somme[l-1].
Problème de la fresque murale
Étiquettes : sommes préfixes
Approche : L'objectif est de trouver un segment continu de longueur fixe (arrondie au supérieur) qui maximise la somme des valeurs. En utilisant un tableau préfixe, on peut calculer la somme de n'importe quel intervalle en temps constant. Il suffit alors de parcourir tous les segments de longueur adéquate et de conserver le maximum.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_SIZE = 5e6 + 5;
char mural[MAX_SIZE];
LL prefix[MAX_SIZE];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int testCases;
cin >> testCases;
for (int caseNum = 1; caseNum <= testCases; caseNum++) {
int length;
cin >> length;
cin >> (mural + 1);
for (int idx = 1; idx <= length; idx++) {
prefix[idx] = prefix[idx - 1] + (mural[idx] - '0');
}
int segmentLen = (length + 1) / 2;
LL bestSum = 0;
for (int start = 1; start + segmentLen - 1 <= length; start++) {
int end = start + segmentLen - 1;
LL currentSum = prefix[end] - prefix[start - 1];
if (currentSum > bestSum) {
bestSum = currentSum;
}
}
cout << "Case #" << caseNum << ": " << bestSum << "\n";
}
return 0;
}
Sommes préfixes - Exemple de base
Étiquettes : sommes préfixes, problème de modèle
Approche : Construction directe du tableau préfixe et réponse aux requêtes d'intervalle.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 100005;
LL cumulative[MAX_N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int value;
cin >> value;
cumulative[i] = cumulative[i - 1] + value;
}
while (m--) {
int left, right;
cin >> left >> right;
cout << cumulative[right] - cumulative[left - 1] << "\n";
}
return 0;
}
Sommes de sous-matrices
Étiquettes : sommes préfixes, matrices
Approche : Étendre le concept aux matrices 2D. On précalcule une matrice préfixe telle que chaque cellule [i][j] contient la somme de tous les éléments du rectangle (1,1) à (i,j). La somme d'un sous-rectengle quelconque se déduit en utilisant le principe d'inclusion-exclusion.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_DIM = 1005;
LL matrixSum[MAX_DIM][MAX_DIM];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int rows, cols, queries;
cin >> rows >> cols >> queries;
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
int elem;
cin >> elem;
matrixSum[i][j] = matrixSum[i - 1][j] + matrixSum[i][j - 1]
- matrixSum[i - 1][j - 1] + elem;
}
}
while (queries--) {
int r1, c1, r2, c2;
cin >> r1 >> c1 >> r2 >> c2;
LL result = matrixSum[r2][c2]
- matrixSum[r2][c1 - 1]
- matrixSum[r1 - 1][c2]
+ matrixSum[r1 - 1][c1 - 1];
cout << result << "\n";
}
return 0;
}
Intervalles multiples de K
Étiquettes : sommes préfixes, congruence modulo
Approche naïve : Vérifier tous les sous-tableaux, complexité O(N^2).
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 100005;
LL prefix[MAX_N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
int val;
cin >> val;
prefix[i] = prefix[i - 1] + val;
}
LL count = 0;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
LL segmentSum = prefix[j] - prefix[i - 1];
if (segmentSum % k == 0) {
count++;
}
}
}
cout << count << "\n";
return 0;
}
Approche optimisée : Utiliser un tableau de comptage des restes modulo K. Pour chaque position j, on ajoute au résultat le nombre d'indices i précédents tels que prefix[i-1] a le même reste que prefix[j] modulo K.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 100005;
LL cumulative[MAX_N];
int remainderCount[MAX_N]; // Supposer k <= MAX_N
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
int num;
cin >> num;
cumulative[i] = cumulative[i - 1] + num;
}
LL validIntervals = 0;
remainderCount[0] = 1; // Pour le préfixe 0
for (int j = 1; j <= n; j++) {
LL currentRemainder = cumulative[j] % k;
if (currentRemainder < 0) currentRemainder += k; // Gérer les négatifs
validIntervals += remainderCount[currentRemainder];
remainderCount[currentRemainder]++;
}
cout << validIntervals << "\n";
return 0;
}
Comptage des sous-matrices
Étiquettes : sommes préfixes, pointeurs
Approche avec pointeurs : Pour chaque paire de lignes (haut et bas), on utilise la technique des deux pointeurs sur les colonnes pour trouver, pour chaque colonne de droite, la colonne de gauche la plus à gauche telle que la somme du rectangle [haut..bas][gauche..droite] ne dépasse pas K.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_DIM = 505;
int grid[MAX_DIM][MAX_DIM];
LL colPrefix[MAX_DIM][MAX_DIM];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, limit;
cin >> n >> m >> limit;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> grid[i][j];
colPrefix[i][j] = colPrefix[i - 1][j] + grid[i][j];
}
}
LL totalCount = 0;
for (int top = 1; top <= n; top++) {
for (int bottom = top; bottom <= n; bottom++) {
LL rowSum = 0;
int leftCol = 1;
for (int rightCol = 1; rightCol <= m; rightCol++) {
rowSum += colPrefix[bottom][rightCol] - colPrefix[top - 1][rightCol];
while (rowSum > limit && leftCol <= rightCol) {
rowSum -= colPrefix[bottom][leftCol] - colPrefix[top - 1][leftCol];
leftCol++;
}
totalCount += (rightCol - leftCol + 1);
}
}
}
cout << totalCount << "\n";
return 0;
}
Triplets croissants
Étiquettes : sommes préfixes, tri, recherche binaire
Approche par recherche binaire : Trier les tableaux A et C. Pour chaque élément de B, compter par recherche binaire le nombre d'éléments dans A inférieurs à B[j] et le nombre d'éléments dans C supérieurs à B[j]. Multiplier ces deux comptages et sommer sur tous les B[j].
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 100005;
int A[MAX_N], B[MAX_N], C[MAX_N];
int countLess(int arr[], int n, int threshold) {
int low = 0, high = n - 1;
int result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] < threshold) {
result = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return result + 1;
}
int countGreater(int arr[], int n, int threshold) {
int low = 0, high = n - 1;
int result = n;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] > threshold) {
result = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return n - result;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> A[i];
for (int i = 0; i < n; i++) cin >> B[i];
for (int i = 0; i < n; i++) cin >> C[i];
sort(A, A + n);
sort(C, C + n);
LL totalTriplets = 0;
for (int j = 0; j < n; j++) {
LL lessA = countLess(A, n, B[j]);
LL greaterC = countGreater(C, n, B[j]);
totalTriplets += lessA * greaterC;
}
cout << totalTriplets << "\n";
return 0;
}
Approche par sommes préfixes : Créer des tableaux de fréquence pour A et C, puis calculer des sommes préfixes pour obtenir rapidement le nombre d'éléments inférieurs ou supérieurs à une valeur donnée.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_VAL = 100002; // Valeurs décalées de 1
int freqA[MAX_VAL], freqC[MAX_VAL];
LL prefixA[MAX_VAL], prefixC[MAX_VAL];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> A(n), B(n), C(n);
for (int& x : A) { cin >> x; x++; freqA[x]++; }
for (int& x : B) cin >> x;
for (int& x : C) { cin >> x; x++; freqC[x]++; }
// Préfixe pour A
for (int i = 1; i < MAX_VAL; i++) {
prefixA[i] = prefixA[i - 1] + freqA[i];
}
// Préfixe pour C
for (int i = 1; i < MAX_VAL; i++) {
prefixC[i] = prefixC[i - 1] + freqC[i];
}
LL result = 0;
for (int j = 0; j < n; j++) {
int val = B[j] + 1; // Décalage
LL countA = prefixA[val - 1];
LL countC = prefixC[MAX_VAL - 1] - prefixC[val];
result += countA * countC;
}
cout << result << "\n";
return 0;
}
Bombe laser
Étiquettes : sommes préfixes, géométrie
Approche : Construire une matrice de cumul des valeurs aux coordonnées données, puis calculer la matrice préfixe 2D. Parcourir tous les carrés de côté R pour trouver le maximum de la somme dans un tel carré.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_COORD = 5005;
LL valueMatrix[MAX_COORD][MAX_COORD];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int targets, radius;
cin >> targets >> radius;
radius = min(radius, MAX_COORD - 1);
for (int i = 0; i < targets; i++) {
int x, y, w;
cin >> x >> y >> w;
x++; y++;
valueMatrix[x][y] += w;
}
// Calcul des sommes préfixes 2D
for (int i = 1; i < MAX_COORD; i++) {
for (int j = 1; j < MAX_COORD; j++) {
valueMatrix[i][j] += valueMatrix[i - 1][j] + valueMatrix[i][j - 1] - valueMatrix[i - 1][j - 1];
}
}
LL maxValue = 0;
for (int x1 = 1; x1 + radius - 1 < MAX_COORD; x1++) {
for (int y1 = 1; y1 + radius - 1 < MAX_COORD; y1++) {
int x2 = x1 + radius - 1;
int y2 = y1 + radius - 1;
LL current = valueMatrix[x2][y2]
- valueMatrix[x2][y1 - 1]
- valueMatrix[x1 - 1][y2]
+ valueMatrix[x1 - 1][y1 - 1];
if (current > maxValue) {
maxValue = current;
}
}
}
cout << maxValue << "\n";
return 0;
}
Tableau tronqué
Étiquettes : sommes préfixes, problèmes de découpe
Approche : Si la somme totale n'est pas divisible par 3, il n'y a aucune solution. Sinon, on parcourt le tableau en comptant le nombre de positions où le préfixe vaut S/3, et pour chaque position où le préfixe vaut 2S/3, on ajoute à la réponse le comptage précédent.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 100005;
LL prefix[MAX_N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int val;
cin >> val;
prefix[i] = prefix[i - 1] + val;
}
LL total = prefix[n];
if (total % 3 != 0) {
cout << 0 << "\n";
} else {
LL third = total / 3;
LL twoThirds = 2 * third;
LL ways = 0;
LL countFirstThird = 0;
for (int i = 1; i < n; i++) {
if (prefix[i] == twoThirds) {
ways += countFirstThird;
}
if (prefix[i] == third) {
countFirstThird++;
}
}
cout << ways << "\n";
}
return 0;
}