Les arbres de segments sont une structure de données fondamentale pour les opérations sur les intervalles, permettant des modifications et requêtes en O(log n). Ils sont particulièrement utiles pour gérer des tableaux dynamiques avec des mises à jour et des calculs sur des plages conitnues.

Structure de base

Un arbre de segments est un arbre binaire où chaque nœud représente un intervalle [debut, fin]. Pour un nœud d'identifiant id, ses fils gauche et droit couvrent respectivement [debut, milieu] et [milieu+1, fin] avec milieu = (debut + fin) / 2. La profondeur de l'arbre est en O(log n), et le nombre total de nœuds est inférieur à 4n.

Construction de l'arbre

La construction initialise les nœuds feuilles avec les valeurs du tableau et combine récursivement les valeurs des fils pour les nœuds parents. Par exemple, pour maintenir la somme d'un tableau tableau de taille n:

void construire_arbre(int debut, int fin, int noeud) {
    if (debut == fin) {
        arbre[noeud].somme = tableau[debut];
        return;
    }
    int milieu = (debut + fin) >> 1;
    construire_arbre(debut, milieu, noeud << 1);
    construire_arbre(milieu + 1, fin, noeud << 1 | 1);
    arbre[noeud].somme = arbre[noeud << 1].somme + arbre[noeud << 1 | 1].somme;
}

La complexité temporelle est en O(n), et l'espace mémoire est en O(n) avec une constante d'environ 4.

Requêtes sur les intervalles

Pour calculer la somme sur un intervalle [l, r], l'algorithme parcourt l'arbre en accumulant les valeurs des nœuds dont l'intervalle est inclus dans la requête. La récursion explore les fils seulement s'ils intersectent l'intervalle demandé.

int requete_somme(int l, int r, int debut, int fin, int noeud) {
    if (l <= debut && fin <= r) return arbre[noeud].somme;
    int milieu = (debut + fin) >> 1, res = 0;
    if (l <= milieu) res += requete_somme(l, r, debut, milieu, noeud << 1);
    if (r > milieu) res += requete_somme(l, r, milieu + 1, fin, noeud << 1 | 1);
    return res;
}

Cette fonction a une complexité en O(log n) car au plus deux nœuds par niveau de l'arbre sont visités dans le pire cas.

Modifications ponctuelles

Pour modifier un seul élément à la position pos en ajoutant une valeur valeur, l'algorithme met à jour tous les ancêtres du nœud feuille correspondant.

void modifier_point(int pos, int valeur, int debut, int fin, int noeud) {
    if (debut == fin) {
        arbre[noeud].somme += valeur;
        return;
    }
    int milieu = (debut + fin) >> 1;
    if (pos <= milieu) modifier_point(pos, valeur, debut, milieu, noeud << 1);
    else modifier_point(pos, valeur, milieu + 1, fin, noeud << 1 | 1);
    arbre[noeud].somme = arbre[noeud << 1].somme + arbre[noeud << 1 | 1].somme;
}

Modifications sur les intervalles avec lazy propagation

Pour appliquer une opération (comme une addition) à tout un intervalle [l, r] en O(log n), on utilise des étiquettes paresseuses. Ces étiquettes stockent les modifications différées qui seront propagées aux fils lors des futures requêtes ou mises à jour.

void appliquer_etiquette(int noeud, int debut, int fin, int valeur) {
    arbre[noeud].somme += (fin - debut + 1) * valeur;
    arbre[noeud].etiquette += valeur;
}

void pousser_etiquette(int noeud, int debut, int fin) {
    if (arbre[noeud].etiquette != 0) {
        int milieu = (debut + fin) >> 1;
        appliquer_etiquette(noeud << 1, debut, milieu, arbre[noeud].etiquette);
        appliquer_etiquette(noeud << 1 | 1, milieu + 1, fin, arbre[noeud].etiquette);
        arbre[noeud].etiquette = 0;
    }
}

void modifier_intervalle(int l, int r, int valeur, int debut, int fin, int noeud) {
    if (l <= debut && fin <= r) {
        appliquer_etiquette(noeud, debut, fin, valeur);
        return;
    }
    pousser_etiquette(noeud, debut, fin);
    int milieu = (debut + fin) >> 1;
    if (l <= milieu) modifier_intervalle(l, r, valeur, debut, milieu, noeud << 1);
    if (r > milieu) modifier_intervalle(l, r, valeur, milieu + 1, fin, noeud << 1 | 1);
    arbre[noeud].somme = arbre[noeud << 1].somme + arbre[noeud << 1 | 1].somme;
}

Lorsque plusieurs opérasions sont combinées (comme multiplication et addition), l'ordre de propagation des étiquettes doit être soigneusement géré pour préserver la cohérence, en appliquant généralement la multiplication avant l'addition.

Variantes importantes

Arbre de Fenwick (Fenwick tree): Une alternative simplifiée pour les requêtes de préfixe et les modifications ponctuelles. Elle utilise une fonction lowbit pour identifier les plages couvertes par chaque nœud.

int lowbit(int x) { return x & (-x); }

void ajouter_fenwick(int x, int valeur) {
    while (x <= n) {
        fenwick[x] += valeur;
        x += lowbit(x);
    }
}

int requete_fenwick(int x) {
    int res = 0;
    while (x > 0) {
        res += fenwick[x];
        x -= lowbit(x);
    }
    return res;
}

Pour maintenir les différences, on peut appliquer les modifications d'intervalle en deux opérations ponctuelles et récupérer les valeurs via des requêtes de préfixe.

Arbre de segments à points dynamiques: Pour gérer de grands domaines de valeurs (jusqu'à 109), les nœuds sont créés à la demande lors de l'accès. Cela réduit l'espace mémoire à O(m log n) où m est le nombre d'opérations.

int prochain_id = 1;
struct NoeudDynamique {
    int gauche = 0, droite = 0;
    long long somme = 0;
    long long etiquette = 0;
} arbre_dynamique[MAX_NOEUDS];

void modifier_dynamique(int l, int r, long long valeur, int &noeud, long long debut, long long fin) {
    if (!noeud) noeud = prochain_id++;
    if (l <= debut && fin <= r) {
        arbre_dynamique[noeud].somme += (fin - debut + 1) * valeur;
        arbre_dynamique[noeud].etiquette += valeur;
        return;
    }
    // Pousser l'étiquette et récursivement modifier les fils
}

Arbre de segments de valeur: Utilisé pour les requêtes basées sur les valeurs (par exemple, compter les occurrences dans une plage de valeurs). Il maintient des fréquences sur le domaine des valeurs, souvent avec des points dynamiques pour les grands espaces.