Introduction aux concepts

La somme préfixée en deux dimensions permet d'obtenir rapidement la somme des éléments dans une sous-matrice spécifique. En revanche, la différence en deux dimensions permet d'ajouter une valeur constante à tous les éléments d'une sous-matrice de manière efficace. Ces deux techniques sont inverses l'une de l'autre.

Somme préfixée en deux dimensions

Calcul de la somme préfixée

Définissons s[i][j] comme la somme des éléments du rectangle allant de (1,1) à (i,j), comme illustré par la zone ombrée ci-dessous.

Pour déterminer la somme d'une sous-matrice dont le coin supérieur gauche est (x_i, y_i) et le coin inférieur droit est (x_j, y_j), on applique le principe d'inclusion-exclusion. En notant cette somme sum :

Voici un exemple de code en C++ qui calcule la somme préfixée et répond à des requêtes de somme de sous-matrices. Les variables ont été renommées pour plus de clarté.

void calculerSommePrefixee() {
    int lignes, colonnes;
    std::cin >> lignes >> colonnes;
    std::vector<:vector>> grille(lignes + 1, std::vector<int>(colonnes + 1, 0));
    std::vector<:vector>> prefixee(lignes + 1, std::vector<int>(colonnes + 1, 0));
    for (int i = 1; i <= lignes; ++i) {
        for (int j = 1; j <= colonnes; ++j) {
            std::cin >> grille[i][j];
        }
    }

    // Calcul de la somme préfixée en deux dimensions
    for (int i = 1; i <= lignes; ++i) {
        for (int j = 1; j <= colonnes; ++j) {
            prefixee[i][j] = prefixee[i - 1][j] + prefixee[i][j - 1] - prefixee[i - 1][j - 1] + grille[i][j];
        }
    }

    // Requête pour la somme de (x1, y1) à (x2, y2)
    int x1, y1, x2, y2;
    std::cin >> x1 >> y1 >> x2 >> y2;
    int somme = prefixee[x2][y2] - prefixee[x2][y1 - 1] - prefixee[x1 - 1][y2] + prefixee[x1 - 1][y1 - 1];
}
</int></:vector></int></:vector>

Différence en deux dimensions

Définition de la différence

Soit le tableau original a[i][j] et le tableau de différence d[i][j]. Leur relation est inverse à celle de la somme préfixée :

Pour ajouter une valeur k à tous les éléments de la sous-matrice allant de (x1, y1) à (x2, y2), on modifie seulement quatre points dans le tableau de différence d :

D'abord, (2,2): +k affecte tous les éléments en bas à droite, comme montré :

Une fois toutes les modifications appliquées à d, on peut reconstruire le tableau final a en calculant la somme préfixée de d.

Reconstruction du tableau original

Pour obtenir a[i][j] à partir de d, on applique la somme préfixée en deux dimensions :

Le processus complet est :

1. Initialiser d à zéro.
2. Pour chaque opération d'ajout de k à une sous-matrice, mettre à jour les quatre points dans d.
3. Calculer la somme préfixée de d pour obtenir le tableau final a.

Implémentation de la différence

Voici un exemple de code en C++ pour la différence en deux dimensions. Les noms de variables ont été modifiés pour une meilleure lisibilité.

void mettreAJourDifference() {
    int lignes, colonnes;
    std::cin >> lignes >> colonnes;
    std::vector<:vector>> matrice(lignes + 1, std::vector<int>(colonnes + 1, 0));
    std::vector<:vector>> difference(lignes + 2, std::vector<int>(colonnes + 2, 0));
    for (int i = 1; i <= lignes; ++i) {
        for (int j = 1; j <= colonnes; ++j) {
            std::cin >> matrice[i][j];
        }
    }

    // Calcul de la différence initiale
    for (int i = 1; i <= lignes; ++i) {
        for (int j = 1; j <= colonnes; ++j) {
            difference[i][j] = matrice[i][j] - matrice[i - 1][j] - matrice[i][j - 1] + matrice[i - 1][j - 1];
        }
    }

    // Mise à jour : ajout de k à la sous-matrice (x1, y1) à (x2, y2)
    int x1, y1, x2, y2, k;
    std::cin >> x1 >> y1 >> x2 >> y2 >> k;
    difference[x1][y1] += k;
    difference[x2 + 1][y1] -= k;
    difference[x1][y2 + 1] -= k;
    difference[x2 + 1][y2 + 1] += k;
}
</int></:vector></int></:vector>