Prérequis : Propriété Distributive

L'application de ces structures de données avancées nécessite que l'opération mathématique sous-jacente satisfasse la propriété distributive. Si l'opération n'est pas distributive, ces algorithmes ne peuvent pas être appliqués.

Arbre de Segments (Segment Tree)

Bien que l'arbre de Fenwick soit plus simple, l'arbre de segments offre une flexibilité supérieure. Il peut résoudre tous les problèmes traités par un arbre de Fenwick, tout en gérant des opérations plus complexes que ce dernier ne supporte pas.

Construction de l'Arbre

Un arbre de segments est un arbre binaire où chaque nœud représente un intervalle spécifique. Les informations de cet intervalle (comme la somme ou le produit) sont déduites de ses nœuds enfants. Voici une implémentation moderne utilisant des tableaux séparés pour optimiser la mémoire et la clarté :

#include <vector>

struct SegTree {
    int n;
    std::vector<long long> sum_tree;
    std::vector<long long> lazy_tree;

    SegTree(int size) : n(size), sum_tree(4 * size, 0), lazy_tree(4 * size, 0) {}

    void build(const std::vector<long long>& arr, int node, int start, int end) {
        if (start == end) {
            sum_tree[node] = arr[start];
            return;
        }
        int mid = (start + end) / 2;
        build(arr, 2 * node, start, mid);
        build(arr, 2 * node + 1, mid + 1, end);
        sum_tree[node] = sum_tree[2 * node] + sum_tree[2 * node + 1];
    }
};

Mise à Jour par Intervalle et Propagation Paresseuse (Lazy Propagation)

Le concept de la propagation paresseuse est le cœur de l'arbre de segments. Lorsqu'un intervalle est entièrement couvert par la mise à jour, on ne modifie pas immédiatement ses enfants. On stocke plutôt la modification dans une balise paresseuse (lazy), qui ne sera propagée aux enfants que lorsque cela sera strictement nécessaire. Cela réduit considérablement la complexité temporelle.

    void apply(int node, int start, int end, long long val) {
        sum_tree[node] += (end - start + 1) * val;
        lazy_tree[node] += val;
    }

    void push_down(int node, int start, int end) {
        if (lazy_tree[node] != 0) {
            int mid = (start + end) / 2;
            apply(2 * node, start, mid, lazy_tree[node]);
            apply(2 * node + 1, mid + 1, end, lazy_tree[node]);
            lazy_tree[node] = 0;
        }
    }

    void update_range(int node, int start, int end, int l, int r, long long val) {
        if (r < start || end < l) return;
        if (l <= start && end <= r) {
            apply(node, start, end, val);
            return;
        }
        push_down(node, start, end);
        int mid = (start + end) / 2;
        update_range(2 * node, start, mid, l, r, val);
        update_range(2 * node + 1, mid + 1, end, l, r, val);
        sum_tree[node] = sum_tree[2 * node] + sum_tree[2 * node + 1];
    }

Requête sur Intervalle

La logique de requête est similaire à la mise à jour. Si l'intervalle du nœud est entièrement contenu dans la requête, on retourne sa valeur. Sinon, on propage les balises paresseuses et on fusionne les résultats des enfants.

    long long query_range(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return 0;
        if (l <= start && end <= r) return sum_tree[node];
        push_down(node, start, end);
        int mid = (start + end) / 2;
        return query_range(2 * node, start, mid, l, r) +
               query_range(2 * node + 1, mid + 1, end, l, r);
    }

Allocation Dynamique de Nœuds

Pour les arbres de segments sur de grands domaines de valeurs, l'allocation dynamique de nœuds permet d'économiser de la mémoire en ne créant les nœuds qu'en cas de besoin. Cette approche s'accompagne souvent de la technique de "marquage permanent" (permanent tagging) pour éviter la propagation paresseuse classique.

Arbre de Fenwick (Binary Indexed Tree)

L'arbre de Fenwick est plus léger en termes de code et de mémoire que l'arbre de segments. Il repose sur la manipulation binaire des indices.

Opération Lowbit et Zones de Gestion

Chaque élément x de l'arbre gère un intervalle de longueur définie par son lowbit. Le lowbit de x correspond à la valeur du bit de poids le plus faible à 1 dans la représentation binaire de x. Il se calcule efficacement via l'opération x & (-x), exploitant la représentation en complément à deux de -x.

Requêtes et Mises à Jour

Les opérations consistent à sauter d'indice en indice en ajoutant ou soustrayant le lowbit.

struct FenwickTree {
    int n;
    std::vector<long long> bit;

    FenwickTree(int size) : n(size), bit(size + 1, 0) {}

    void point_update(int idx, long long delta) {
        for (; idx <= n; idx += idx & (-idx)) {
            bit[idx] += delta;
        }
    }

    long long prefix_query(int idx) {
        long long res = 0;
        for (; idx > 0; idx -= idx & (-idx)) {
            res += bit[idx];
        }
        return res;
    }

    long long range_query(int l, int r) {
        return prefix_query(r) - prefix_query(l - 1);
    }
};

Pour les mises à jour par intervalle, on combine généralement l'arbre de Fenwick avec un tableau de différences. L'arbre de Fenwick peut également être étendu à deux dimensions en ajoutant simplement une boucle imbriquée pour le deuxième indice.

Arbre de Segments de Valeurs (Value Segment Tree)

Un arbre de segments de valeurs ne stocke pas les éléments dans leur ordre original, mais enregistre la fréquence de chaque valeur dans un domaine donné. Il est souvent nécessaire de discrétiser les valeurs si le domaine est trop grand.

Recherche du k-ième Plus Petit Élément

Au lieu d'utiliser une recherche binaire classique qui donne une complexité de O(log² n), on peut utiliser une approche par multiplication (binary lifting) pour atteindre O(log n). En partant de la racine, on évalue la somme des enfants gauches. Si cette somme est inférieure à k, on soustrait cette somme de k et on descend à droite. Sinon, on descend à gauche.

Calcul des Inversions Globales

Après discrétisation, on parcourt le tableau à l'envers. Pour chaque élément x, on interroge l'arbre de Fenwick pour obtenir la somme des fréquences dans l'intervalle [1, x-1], ce qui donne le nombre d'éléments plus petits apparus après x. On incrémente ensuite la fréquence de x dans l'arbre.

Décomposition par Blocs (Square Root Decomposition)

La décomposition par blocs divise la séquence en blocs de taille S. La complexité optimale est atteinte lorsque S ≈ √n, équilibrant le traitement des blocs complets et des éléments isolés.

Implémentation des Opérations

Pour une mise à jour ou une requête sur un intervalle [l, r] : si l et r sont dans le même bloc, on traite les éléments individuellement. Sinon, on traite les éléments des blocs partiels aux extrémités individuellement, et on applique une modification globale (via une balise paresseuse de bloc) pour les blocs entièrement contenus dans l'intervalle.

#include <vector>
#include <cmath>

struct BlockDecomp {
    int n, block_size;
    std::vector<long long> arr;
    std::vector<long long> block_sum;
    std::vector<long long> block_lazy;
    std::vector<int> block_id;

    BlockDecomp(const std::vector<long long>& input) {
        n = input.size();
        arr = input;
        block_size = std::max(1, (int)std::sqrt(n));
        int num_blocks = (n + block_size - 1) / block_size;
        block_sum.assign(num_blocks, 0);
        block_lazy.assign(num_blocks, 0);
        block_id.resize(n);

        for (int i = 0; i < n; ++i) {
            block_id[i] = i / block_size;
            block_sum[block_id[i]] += arr[i];
        }
    }

    void range_add(int l, int r, long long val) {
        int id_l = block_id[l], id_r = block_id[r];
        if (id_l == id_r) {
            for (int i = l; i <= r; ++i) {
                arr[i] += val;
                block_sum[id_l] += val;
            }
        } else {
            for (int i = l; block_id[i] == id_l; ++i) {
                arr[i] += val;
                block_sum[id_l] += val;
            }
            for (int b = id_l + 1; b < id_r; ++b) {
                block_lazy[b] += val;
                block_sum[b] += val * block_size;
            }
            for (int i = id_r * block_size; i <= r; ++i) {
                arr[i] += val;
                block_sum[id_r] += val;
            }
        }
    }

    long long range_sum(int l, int r) {
        long long res = 0;
        int id_l = block_id[l], id_r = block_id[r];
        if (id_l == id_r) {
            for (int i = l; i <= r; ++i) {
                res += arr[i] + block_lazy[id_l];
            }
        } else {
            for (int i = l; block_id[i] == id_l; ++i) {
                res += arr[i] + block_lazy[id_l];
            }
            for (int b = id_l + 1; b < id_r; ++b) {
                res += block_sum[b];
            }
            for (int i = id_r * block_size; i <= r; ++i) {
                res += arr[i] + block_lazy[id_r];
            }
        }
        return res;
    }
};