Les problèmes de calcul de sommes sur des sous-ensembles ou des sur-ensembles d'un ensemble binaire sont courants en algorithmique. Deux approches principales existent : l'énumération directe (complexité O(3^n) dans le pire cas) et la propagation de contributions via des techniques de programmation dynamique. Cette dernière, connue sous le nom de DP sur les sous-ensembles (SOS DP), permet de calculer efficacement des sommes préfixées multidimensionnelles.

Énumération des sous-ensembles

Énumérer tous les sous-ensembles d'un masque binaire u peut être fait de manière optimale avec la boucle suivante, où chaque sous-ensemble est traité exactement une fois :

int masque = u;
while (masque) {
    // traiter masque comme un sous-ensemble
    masque = (masque - 1) & u;
}
// ne pas oublier de traiter le sous-ensemble vide si nécessaire

Cette technique évite les répétitions et offre une complexité totale de O(3^n) pour tous les masques.

Graphes et DAG des sous-ensembles

La relation d'inclusion entre sous-ensembles forme un graphe acyclique dirigé (DAG). Une tentative naïve de calcul de sommes via ce graphe peut conduire à des double-comptages, car un même sous-ensemble peut être atteint par plusieurs chemins. Par exemple, pour le masque 111, la somme via 110 et 101 inclurait deux fois 100. Une transformation en arbre, en conservant uniquement les arêtes vers la couche inférieure la plus à gauche, évite ce problème mais ne réduit pas la complexité globale.

Somme préfixée multidimensionnelle

La somme préfixée multidimensionnelle étend le concept aux dimensions où chaque axe a deux états (0 ou 1), correspondant aux bits d'un masque. Soit f[S] la valeur pour le masque S, on souhaite calculer g[S] = somme f[T] pour T ⊆ S. Une approche par inclusion-exclusion est possible mais moins efficace. À la place, le SOS DP procède dimension par dimension, similaire à un jeu de 2048 multidimensionnel.

SOS DP pour les sommations

L'idée fondamentale est de propager les contributions bit par bit. Pour calculer la somme préfixée (sous-ensembles), on met à jour les masques qui ont le bit k activé en ajoutant la contribution des masques sans ce bit. Inversement, pour la somme suffixée (sur-ensembles), on met à jour les masques sans le bit k. Voici les implémentations typiques avec des variables renommées :

// Somme préfixée : g[S] = somme f[T] pour T ⊆ S
void calculer_somme_prefixee(vector<long long="">& g, int nb_bits) {
    for (int bit = 0; bit < nb_bits; ++bit) {
        for (int masque = 0; masque < (1 << nb_bits); ++masque) {
            if (masque & (1 << bit)) {
                g[masque] += g[masque ^ (1 << bit)];
            }
        }
    }
}

// Somme suffixée : g[S] = somme f[T] pour S ⊆ T
void calculer_somme_suffixee(vector<long long="">& g, int nb_bits) {
    for (int bit = 0; bit < nb_bits; ++bit) {
        for (int masque = 0; masque < (1 << nb_bits); ++masque) {
            if (!(masque & (1 << bit))) {
                g[masque] += g[masque ^ (1 << bit)];
            }
        }
    }
}</long></long>

La différence entre préfixée et suffixée réside dans la dierction de la propagation : vers les masques avec le bit activé ou désactivé. Une inversion des bits échange les rôles des sous-ensembles et sur-ensembles.

Application : recherche de nombres compatibles

Considérons le problème où l'on doit trouver, pour chaque nombre dans une liste, un autre nombre tel que leur ET logique soit zéro. Un nombre est compatible avec x s'il est un sous-ensemble du complément de x. En calculant une somme préfixée sur les valeurs initiales (avec une opération de remplacement plutôt que d'addition), on peut répondre aux requêtes en consultant la valeur pour le complément.

Différence multidimensionnelle

L'opération inverse de la somme préfixée est la différence multidimensionnelle. Étant donné le tableau g représentant les sommes, on récupère le tableau original f en inversant la propagation, en utilisant la soustraction au lieu de l'addition. Par exemple, pour la différence préfixée :

// Différence préfixée : recouvre f à partir de g
void calculer_difference_prefixee(vector<long long="">& f, int nb_bits) {
    for (int bit = 0; bit < nb_bits; ++bit) {
        for (int masque = 0; masque < (1 << nb_bits); ++masque) {
            if (masque & (1 << bit)) {
                f[masque] -= f[masque ^ (1 << bit)];
            }
        }
    }
}</long>

Cette technique est utile lorsque le tableau des sommes est plus facile à obtenir que le tableau original.

Application : comptage de sous-séquences avec ET nul

Dans un problème où l'on doit compter les sous-séquences dont le ET logique est zéro, on peut définir num_S comme le nombre d'éléments contenant le masque S. La somme suffixée de ces comptages donne le nombre de sous-séquences dont le ET est un sur-ensemble de S. En appliquant une différence suffixée, on obtient les comptages exacts pour chaque résultat possible, et la réponse est la valeur pour le masque zéro.

Ces techniques de SOS DP et de sommes multidimensionnelles sont fondamentales pour résoudre efficacement des problèmes combinatoires sur des espaces de masques binaires.