Le problème consiste à identifier le sous-tableau, au sein d'un tableau d'entiers donné, dont la somme XOR (ou exclusif) est la plus élevée possible. Si le tableau d'entrée contient n nombres, l'objectif est de trouver max(a[i] ^ a[i+1] ^ ... ^ a[j]) pour tous les 0 <= i <= j < n.

Format d'entrée

La première ligne contient un entier n, représentant la dimension du tableau.

La ligne suivante contient n entiers x1, x2, ..., xn, constituant les éléments du tableau.

Format de sortie

Un entier unique, correspondant à la somme XOR maximale d'un sous-tableau.

Exemple d'entrée

4
5 1 5 9

Exemple de sortie

13

Implémentation en C++

#include <iostream>
#include <vector>
#include <algorithm> // Pour std::max

// Définition de constantes pour la taille maximale du tableau et le nombre de nœuds du Trie.
// Un nombre sur 32 bits a au plus 32 niveaux dans le Trie.
// Pour 10^5 éléments, il y aura au maximum 10^5 préfixes XOR.
// Le nombre total de nœuds est environ 32 * 10^5.
const int MAX_NOEUDS_TRIE = 32 * 100000 + 10;
const int MAX_TAILLE_ARRAY = 100000 + 5;

// noeudsTrie[n][0/1] représente l'enfant 0 ou 1 du nœud n.
// compteurNoeuds suit le prochain identifiant de nœud disponible.
int noeudsTrie[MAX_NOEUDS_TRIE][2];
int compteurNoeuds = 1; // Le nœud racine est 1.

// La fonction 'insererNombre' ajoute la représentation binaire d'un nombre au Trie.
void insererNombre(int val) {
    int noeudCourant = 1; // Commencer à la racine.
    // Parcourir les bits de poids fort à poids faible (pour un entier 32 bits).
    for (int i = 30; i >= 0; --i) {
        int bit = (val >> i) & 1; // Extraire le i-ème bit.
        if (!noeudsTrie[noeudCourant][bit]) {
            // Si le chemin pour ce bit n'existe pas, créer un nouveau nœud.
            noeudsTrie[noeudCourant][bit] = ++compteurNoeuds;
        }
        noeudCourant = noeudsTrie[noeudCourant][bit]; // Se déplacer vers le nœud enfant.
    }
}

// La fonction 'rechercherMaxXOR' trouve le nombre dans le Trie qui maximise l'opération XOR avec 'val'.
int rechercherMaxXOR(int val) {
    int noeudCourant = 1; // Commencer à la racine.
    int resultatXOR = 0; // Initialiser le résultat XOR maximal trouvé.
    for (int i = 30; i >= 0; --i) {
        int bit = (val >> i) & 1; // Extraire le i-ème bit de 'val'.
        // Pour maximiser le XOR, nous voulons un bit opposé.
        if (noeudsTrie[noeudCourant][1 - bit]) {
            // Si un enfant avec le bit opposé existe, prendre ce chemin.
            noeudCourant = noeudsTrie[noeudCourant][1 - bit];
            resultatXOR |= (1 << i); // Cela signifie que le i-ème bit du résultat XOR est 1.
        } else {
            // Sinon, nous devons prendre le chemin avec le même bit.
            noeudCourant = noeudsTrie[noeudCourant][bit];
        }
    }
    return resultatXOR; // Retourner la valeur XOR maximale.
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    std::vector<int> donnees(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> donnees[i];
    }

    // Calculer les sommes XOR de préfixes.
    // xorPrefixes[i] = a[0] ^ a[1] ^ ... ^ a[i-1]
    std::vector<int> xorPrefixes(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        xorPrefixes[i + 1] = xorPrefixes[i] ^ donnees[i];
    }

    // Insérer 0 dans le Trie. Cela permet de considérer les sous-tableaux
    // qui commencent au tout début du tableau (a[0...k-1]).
    insererNombre(0);

    int maxGlobalXOR = 0; // Suivre le résultat XOR maximal.
    for (int i = 1; i <= n; ++i) {
        // Pour chaque somme XOR de préfixes P_i, rechercher P_j dans le Trie
        // tel que P_i ^ P_j soit maximal.
        // P_i ^ P_j représente la somme XOR du sous-tableau a[j...i-1].
        maxGlobalXOR = std::max(maxGlobalXOR, rechercherMaxXOR(xorPrefixes[i]));
        // Ajouter P_i au Trie pour les recherches futures.
        insererNombre(xorPrefixes[i]);
    }

    std::cout << maxGlobalXOR << std::endl;

    return 0;
}
</int></int>

Analyse du code

1. Pourquoi la taille de la structure Trie est-elle si grande ?

La constante MAX_NOEUDS_TRIE est définie comme 32 * 100000 + 10. Cette valeur découle du nombre maximal possible de nœuds danss un Trie binaire :

• Chaque nombre entier (généralement int) est représenté sur 32 bits.
• Nous traitons au maximum n sommes XOR de préfixes (où n peut aller jusqu'à 10^5).
• Dans le pire des cas, chaque insertion d'un nouveau nombre dans le Trie pourrait créer jusqu'à 32 nouveaux nœuds si le chemin binaire de ce nombre est entièrement nouveau.

Ainsi, le nombre maximal de nœuds est environ 32 * n. Pour n = 10^5, cela donne 32 * 10^5 = 3 200 000 nœuds. La valeur 32 * 100000 + 10 est une marge suffisante pour contenir tous les nœuds nécessaires.

2. Initialisation des nœuds du Trie : noeudCourant = 1, compteurNoeuds = 1

• noeudCourant = 1 : Dans notre implémentation, le nœud racine du Trie est désigné par l'identifiant 1. La variable noeudCourant est utilisée pour naviguer dans l'arbre, et elle commence toujours à la racine lors d'une nouvelle opération (insertion ou recherche).
• compteurNoeuds = 1 : Cette variable gère l'attribution d'identifiants uniques aux nouveaux nœuds. Initialement, seul le nœud racine (1) existe. Chaque fois qu'un nouveau nœud est créé, compteurNoeuds est incrémenté, et sa nouvelle valeur est attribuée au nœud, garantissant l'unicité de l'identifiant.

3. Interprétation de l'opération resultatXOR |= (1 << i)

L'opération resultatXOR |= (1 << i) est une opération bit à bit qui met à 1 le i-ème bit de la varible resultatXOR, tout en laissant les autres bits inchangés. Son rôle est crucial dans la fonction rechercherMaxXOR :

• Lorsque le programme tente de trouver la valeur qui maximise le XOR avec val, il parcourt les bits de val de gauche à droite.
• Si le i-ème bit de val est b, le chemin optimal dans le Trie serait de prendre l'enfant correspondant au bit 1 - b. Si un tel enfant existe, cela signifie que le i-ème bit de la valeur trouvée est 1 - b. Par conséquent, le i-ème bit de val ^ (valeur_trouvée) sera b ^ (1 - b) = 1.
• C'est dans ce cas que resultatXOR |= (1 << i) est exécuté, indiquant que le i-ème bit du résultat XOR maximal est bien 1.

4. Justification de l'insertion de la valeur zéro dans le Trie

L'insertion initiale de 0 dans le Trie est essentielle pour gérer correctement les sous-tableaux qui commencent au tout début du tableau d'origine. Soit P_k la somme XOR des k premiers éléments (a[0] ^ ... ^ a[k-1]).

• La somme XOR d'un sous-tableau a[j...i-1] est donnée par P_i ^ P_j.
• Si nous voulons considérer un sous-tableau qui commence à l'indice 0 (par exemple, a[0...k-1]), cela équivaut à calculer P_k ^ P_0.
• Comme P_0 représente la somme XOR d'un tableau vide, sa valeur est 0.
• En insérant 0 dans le Trie, nous nous assurons que P_0 est disponible pour la fonction rechercherMaxXOR, permettant ainsi de considérer la somme XOR de tout préfixe du tableau original (P_k ^ 0 = P_k) comme un candidat pour le maximum global. Sans cela, les sous-tableaux commençant à l'indice 0 seraient ignorés.

5. L'intérêt des sommes XOR de préfixes

Le problème demande de trouver la somme XOR maximale de n'importe quel sous-tableau a[j...i-1]. Plutôt que de calculer le XOR pour chaque sous-tableau possible (ce qui serait inefficace avec une complexité en O(N^2) ou O(N^3)), nous utilisons la technique des sommes XOR de préfixes :

• Définissons P_k comme la somme XOR des k premiers éléments : P_k = a[0] ^ a[1] ^ ... ^ a[k-1]. Par convention, P_0 = 0.
• La somme XOR d'un sous-tableau a[j...i-1] peut alors être exprimée comme P_i ^ P_j.
• En précalculant toutes les sommes XOR de préfixes P_k, le problème se réduit à trouver max(P_i ^ P_j) pour tous 0 <= j < i <= N.
• Cela transforme le problème de la recherche d'une somme de sous-tableau en la recherche d'une paire de sommes de préfixes qui maximisent leur XOR mutuel.

6. Passage de xorPrefixes\[i\] à la fonction de requête

Dans la boucle principale, nous appelons rechercherMaxXOR(xorPrefixes[i]) pour chaque xorPrefixes[i]. Cette étape est cruciale :

• Pour chaque P_i = xorPrefixes[i], nous cherchons un P_j qui a déjà été inséré dans le Trie (c'est-à-dire j < i) tel que P_i ^ P_j soit le plus grand possible.
• La fonction rechercherMaxXOR est conçue précisément pour trouver ce P_j optimal.
• Le résultat de cette requête est la somme XOR maximale d'un sous-tableau se terminant à l'indice i-1. Le maxGlobalXOR est ensuite mis à jour avec cette valeur.

7. Pourquoi stocker les sommes XOR de préfixes et non les éléments bruts ?

La question du problème est de trouver la somme XOR maximale d'un sous-tableau, pas d'un simple élément ou d'une paire d'éléments. Insérer les éléments individuels a[k] dans le Trie ne nous permettrait pas de calculer la somme XOR de sous-tableaux de manière efficace :

• Le Trie binaire est optimisé pour trouver des valeurs qui maxiimsent le XOR avec une valeur donnée.
• En insérant les sommes XOR de préfixes (P_k), nous transformons le problème du sous-tableau en un problème de paire de sommes de préfixes (P_i ^ P_j). Chaque P_i ^ P_j représente précisément la somme XOR d'un sous-tableau.
• Ainsi, le Trie est utilisé pour rechercher, pour un P_i donné, le P_j qui a été rencontré précédemment et qui, lorsqu'on le XOR avec P_i, donne le plus grand résultat. Ce résultat est la somme XOR d'un sous-tableau.