Préliminaires : Préfixe-somme en faible dimension

Revenons aux fondamentaux avec les préfixe-sommes unidimensionnelles et bidimensionnelles.

1. Préfixe-somme unidimensionnelle

Soit un tableau t[1...n], on calcule la préfixe-somme ps[i] = t[1] + ... + t[i] par une simple boucle :

for idx from 1 to n:
    ps[idx] = ps[idx - 1] + t[idx]

L'essentiel est que ps[i] agrège la somme de tous les éléments dont l'indice ne dépasse pas i.

2. Préfixe-somme bidimensionnelle

Pour une matrice m[i][j], la préfixe-somme ps2d[i][j] représente la somme des éléments dans le rectangle défini de (1,1) à (i,j). La formule récursive s'écrit :

ps2d[i][j] = ps2d[i-1][j] + ps2d[i][j-1] - ps2d[i-1][j-1] + m[i][j]

Cette formulation repose sur le principe d'inclusion-exclusion. On note que ps2d[i][j] cumule les éléments où la première coordonnée x ≤ i et la seconde y ≤ j.

Une approche alternative pour la préfixe-somme 2D

Examinons une méthode progressive pour calculer cette somme.

Phase 1 : Appliquer une préfixe-somme unidimensionnelle sur chaque ligne pour les colonnes.

for i from 1 to lignes:
    for j from 1 to colonnes:
        m[i][j] = m[i][j] + m[i][j-1]

À l'issue, m[i][j] contient la somme des éléments de la ligne i de la colonne 1 à j.

Phase 2 : Ensuite, appliquer une préfixe-somme unidimensionnelle sur chaque colonne pour les lignes.

for j from 1 to colonnes:
    for i from 1 to lignes:
        m[i][j] = m[i][j] + m[i-1][j]

Ainsi, m[i][j] final correspond à la préfixe-somme bidimensionnelle souhaitée. Ce processus séquentiel se généralise aisément à des dimensions supérieures.

Généralisation en haute dimension

Considérons un tableau à D dimensions a[i1][i2]...[iD]. La préfixe-somme psd[i1][i2]...[iD] est la somme sur tous les indices xk ≤ ik pour chaque dimesnion k.

L'algorithme consiste à itérer sur chaque dimension pour y appliquer une préfixe-somme unidimensionnelle.

// Pseudo-code pour la préfixe-somme multidimensionnelle
for dim from 1 to D:
    for coord1 from 1 to taille1:
        for coord2 from 1 to taille2:
            ...
            for coordD from 1 to tailleD:
                if coord_dim > 1:
                    a[coord1]...[coord_dim]...[coordD] += a[coord1]...[coord_dim-1]...[coordD]

La complexité temporelle est O(D * taille1 * taille2 * ... * tailleD).

Application aux sommes sur les sous-ensembles (SOS DP)

Dans les problèmes de manipulation de bits, on cherche souvent à calculer la somme de tous les sous-ensembles d'un masque binaire. Étant donné un tableau v[0...2^N-1], on définit s[m] = somme de v[ss] pour tous les sous-ensembles ss de m (c'est-à-dire ss | m == m).

Cette tâche équivaut à une préfixe-somme dans un espace à N dimensions, où chaque dimension ne prend que deux valeurs (0 ou 1). Un masque m est interprété comme un point (b_{N-1}, ..., b_0) dans cet espace.

Voici une implémentation typique de SOS DP :

// Initialisation avec le tableau d'origine
for (int masque = 0; masque < (1 << N); ++masque) {
    somme[masque] = valeur[masque];
}

// Traitement dimension par dimension
for (int bit = 0; bit < N; ++bit) {
    for (int masque = 0; masque < (1 << N); ++masque) {
        if (masque & (1 << bit)) {
            somme[masque] += somme[masque ^ (1 << bit)];
        }
    }
}

La complexité de cette méthode est O(N * 2^N), ce qui est efficace pour des valeurs de N raisonnables.

Récapitulatif des concepts fondamentaux

• La préfixe-somme multidimensionnelle étend le concept unidimensionnel en traitant les dimensions de manière séquentielle.
• L'approche SOS DP exploite cette technique pour résoudre des problèmes de sommes sur les sous-ensembles via la manipulation de bits.
• Cette méthode est cruciale en algorithmique avancée pour gérer les ensembles et les masques binaires.