Bases linéaires sur GF(2)
Définition formelle
Une base linéaire est un ensemble construit à partir d'une séquence de nombres, vérifiant deux propriétés fondamentales :
- L'ensemble de toutes les valeurs XOR obtenues en choisissant des sous-ensembles arbitraires de la base est identique à celui de la séquence originale.
- La base est le plus petit ensemble satisfaisant la propriété précédente.
On en déduit les conséquences suivantes :
- Tout élément de la séquence initiale peut être exprimé comme la combinaison XOR de certains éléments de la base.
- Aucun sous-ensemble non vide de la base ne produit un XOR nul (sinon on pourrait retirer un élément sans modifier l'ensemble des XOR, violant la minimalité).
- Deux sous-ensembles distincts de la base ne peuvent jamais engendrer le même résultat XOR.
Construction incrémentale
On procède par insertion successive. On note base[i] le vecteur de base dont le bit le plus significatif se trouve en position i.
Lorsqu'on tente d'insérer un nombre x, on parcourt les bits du plus significatif au moins significatif. Si le bit courant de x est à 1 et qu'un vecteur de base existe déjà en cette position, on applique un XOR pour annuler ce bit. Si aucun vecteur n'existe en cette position, on y place x. Si x se réduit à zéro, il est déjà représentable par la base courante.
void insert_element(long long val) {
for (int bit = 63; bit >= 0; --bit) {
if (!((val >> bit) & 1)) continue;
if (!basis[bit]) {
basis[bit] = val;
return;
}
val ^= basis[bit];
}
}
Complexité temporelle : O(n log V) où V est la valeur maximale.
Extraction du maximum XOR
Pour obtenir la plus grande valeur XOR réalisable à partir de la base, on parcourt les positions de haut en bas et on applique un XOR si cela augmente le résultat courant :
long long compute_max_xor() {
long long result = 0;
for (int bit = 63; bit >= 0; --bit) {
result = max(result, result ^ basis[bit]);
}
return result;
}
La stratégie repose sur un glouton bit à bit : en position i, si le bit de result vaut 0, on applique systématiquement le XOR avec basis[i] pour positionner ce bit à 1.
Fusion de deux bases
La fusion est réalisée en insérant systématiquement tous les éléments d'une base dans l'autre.
Tri et optimisation gloutonne
Certains problèmes exigent de maximiser une somme de poids tout en conservant la propriété de base linéaire. Puisque l'ordre d'insertion n'affecte pas la base finale, on trie simplement les éléments par poids décroissant avant insertion.
Une variante alternative consiste, lors de l'insertion, à échanger l'élément courant avec celui déjà en place si son poids est supérieur :
void insert_with_weight(int idx) {
for (int bit = 62; bit >= 0 && elements[idx].value; --bit) {
if (!((elements[idx].value >> bit) & 1)) continue;
if (!basis_pos[bit]) {
basis_pos[bit] = idx;
return;
}
if (elements[idx].weight > elements[basis_pos[bit]].weight) {
swap(idx, basis_pos[bit]);
}
elements[idx].value ^= elements[basis_pos[bit]].value;
}
}
Comptage des valeurs XOR distinctes
Si la base contient k éléments linéairement indépendants, le nombre total de valeurs XOR distinctes accessibles vaut exactement 2^k.
Application aux graphes
Pour trouver le plus grand XOR le long de chemins dans un graphe, on effectue un DFS pour identifier tous les cycles, on injecte leurs poids XOR dans une base linéaire, puis on interroge cette base pour le maximum.
Recherche du k-ième élément
Cas statique global
Pour une requête unique, on utilise nth_element. Pour des requêtes multiples, un tri préalable suffit.
Cas dynamique global
On emploie un arbre équilibré ou une recherche binaire sur un arbre de segments de valeurs.
Cas statique sur intervalle
La technique classique repose sur un arbre de segments persistant (arbre principal) combiné à une recherche binaire.
Pour une requête sur l'intervalle [l, r], on soustrait la version r de la version l-1 pour obtenir l'arbre correspondant aux éléments de l'intervalle :
int query_kth(int node_r, int node_l, int lo, int hi, int k) {
if (lo == hi) return lo;
int left_count = seg[seg[node_r].left].count - seg[seg[node_l].left].count;
int mid = (lo + hi) >> 1;
if (left_count >= k)
return query_kth(seg[node_r].left, seg[node_l].left, lo, mid, k);
else
return query_kth(seg[node_r].right, seg[node_l].right, mid + 1, hi, k - left_count);
}
Cas dynamique sur intervalle
Pour le traitement en ligne, on utilise un arbre imbriqué : un arbre de Fenwick encapsulant des arbres de segments de valeurs, des tries binaires 01, ou des vecteurs triés.
Pour le traitement hors ligne, la bisection globale est une approche efficacee. On traite toutes les requêtes simultanément en subdivisant récursivement l'espace des valeurs :
void global_bisect(int val_lo, int val_hi, int ql, int qr) {
if (val_lo == val_hi) {
for (int i = ql; i <= qr; ++i)
if (queries[i].type == QUERY)
answers[queries[i].id] = val_lo;
return;
}
int mid_val = (val_lo + val_hi) >> 1;
int split = ql;
for (int i = ql; i <= qr; ++i) {
if (queries[i].type == QUERY) {
int cnt = fenwick_range(queries[i].right) - fenwick_range(queries[i].left - 1);
if (queries[i].k <= cnt)
buffer[split++] = queries[i];
else {
queries[i].k -= cnt;
buffer[--qr_actual] = queries[i];
}
} else {
if (queries[i].position <= mid_val)
fenwick_update(queries[i].index, queries[i].delta),
buffer[split++] = queries[i];
else
buffer[--qr_actual] = queries[i];
}
}
// Annulation des mises à jour de Fenwick
for (int i = ql; i < split; ++i)
if (queries[i].type == MODIFY && queries[i].position <= mid_val)
fenwick_update(queries[i].index, -queries[i].delta);
// Copie du buffer dans le tableau original
// Appels récursifs
global_bisect(val_lo, mid_val, ql, split - 1);
global_bisect(mid_val + 1, val_hi, split, qr_actual);
}
k-ième somme de paires
Étant deux séquences triées, on forme un tableau de paires. On initialise une file de priorité avec le premier élément de chaque ligne. À chaque extractino du minimum, on insère l'élément suivant de la même ligne. Complexité : O(k log n).
k-ième somme de sous-tableau
La somme d'un intervalle correspond à la différence de préfixes. Pour chaque position, on utilise une table de préfixes et une structure de type ST-table pour maitnenir les maximums, en exploitant une file de priorité pour itérer sur les candidats.
Structures de données persistantes
Arbre de segments persistant
L'idée centrale est de ne copier que les nœuds réellement modifiés lors d'une opération, en réutilisant au maximum l'information des versions antérieures. Chaque mise à jour crée un chemin de O(log n) nouveaux nœuds.
void persistent_update(int old_node, int &new_node, int lo, int hi, int pos, int val) {
new_node = ++node_count;
tree[new_node] = tree[old_node];
if (lo == hi) { tree[new_node].value = val; return; }
int mid = (lo + hi) >> 1;
if (pos <= mid)
persistent_update(tree[old_node].left, tree[new_node].left, lo, mid, pos, val);
else
persistent_update(tree[old_node].right, tree[new_node].right, mid + 1, hi, pos, val);
}
Trie 01 persistant
Le trie 01 persistant offre des capacités supérieures aux arbres équilibrés persistants pour la gestion de valeurs numériques : il supporte insertion, suppression, prédécesseur, successeur, k-ième élément et rang, le tout nativement avec les opérations XOR.
Pour les requêtes sur un intervalle [l, r], on utilise deux versions du trie (r et l-1) et on effectue une bisection simultanée sur les deux racines.
Arbre équilibré persistant (FHQ Treap)
La persistance est obtenue en copiant systématiquement les nœuds lors des opérations de split et merge :
void copy_node(int dest, int src) {
left[dest] = left[src]; right[dest] = right[src];
size[dest] = size[src]; value[dest] = value[src]; priority[dest] = priority[src];
}
void split(int node, int key, int &a, int &b) {
if (!node) { a = b = 0; return; }
copy_node(++node_count, node); node = node_count;
if (value[node] <= key) {
a = node;
split(right[node], key, right[a], b);
pull(a);
} else {
b = node;
split(left[node], key, a, left[b]);
pull(b);
}
}
int merge(int x, int y) {
if (!x || !y) return x | y;
int rt = ++node_count;
if (priority[x] < priority[y]) {
copy_node(rt, x);
right[rt] = merge(right[rt], y);
pull(rt);
} else {
copy_node(rt, y);
left[rt] = merge(x, left[rt]);
pull(rt);
}
return rt;
}
Arbres imbriqués
Principe général
Les arbres imbriqués traitent les problèmes de modifications ponctuelles et requêtes rectangulaires (ou l'inverse) sur des données bidimensionnelles. Chaque nœud de l'arbre extérieur maintient une structure interne complète.
Arbre de Fenwick + trie 01
L'arbre de Fenwick identifie O(log n) structures internes affectées par une opération. Pour le k-ième élément sur un intervalle, on collecte les racines des arbres correspondant aux extrémités, puis on effectue une bisection multi-arbre :
int multi_tree_kth(int bit, int k, int accumulated, vector<int> &roots_r, vector<int> &roots_l) {
if (bit < 0) return accumulated;
int left_sum = 0;
for (int r : roots_r) left_sum += tree[child[r][0]].count;
for (int l : roots_l) left_sum -= tree[child[l][0]].count;
bool go_right = (left_sum < k);
for (int &r : roots_r) r = child[r][go_right];
for (int &l : roots_l) l = child[l][go_right];
if (go_right) k -= left_sum;
return multi_tree_kth(bit - 1, k, accumulated | (go_right << bit), roots_r, roots_l);
}
Arbre de Fenwick + vecteur trié
Sur des données aléatoires, remplacer la structure interne par des vecteurs triés avec lower_bound offre d'excellentes performances avec un code beaucoup plus simple et une empreinte mémoire réduite.
Arbre de Fenwick + arbre de segments (Arbre principal dynamique)
L'arbre principal statique utilise un tableau de préfixes pour accéder rapidement à l'information d'un intervalle. En remplaçant ce tableau de préfixes par un arbre de Fenwick, on obtient une structure capable de gérer les modifications dynamiques tout en conservant la recherche binaire sur l'arbre de segments de valeurs.
Problèmes d'application : requêtes de k-ième minimum dynamique, inversions dynamiques dans une permutation, et divers problèmes d'ordre partiel sur des intervalles modifiables.