Principe fondamental

Transformer un arbre en une séquence linéaire où n'importe quel chemin correspond à au plus O(log n) segments consécutifs.

Définitions essentielles

• Fils lourd : enfant dont la sous-arbre contient le plus de nœuds
• Fils léger : tout enfant n'étant pas fils lourd
• Arête lourde : reliant un nœud à son fils lourd
• Arête légère : reliant un nœud à un fils léger
• Chaîne lourde : séquence maximale d'arêtes lourdes connectées

Construire l'ordonnancement

Prioriesr la visite des fils lourds durant le parcours DFS garantit que tous les nœuds d'une même chaîne lourde apparaissent consécutivement dans la séquence.

Théorème central

Tout chemin arbitraire dans l'arbre peut être décomposé en au plus O(log n) chaînes lourdes, soit O(log n) intervalles continus.

Complexité temporelle

Requête ponctuelle : O(log² n)

Implémentation de référence

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int MAX_NODES = 100005;

vector<int> adj[MAX_NODES];
int valeur[MAX_NODES], ordre_id[MAX_NODES], valeur_seg[MAX_NODES];
int compteur, profondeur[MAX_NODES], taille[MAX_NODES];
int tete[MAX_NODES], parent[MAX𝙋𝙤𝙞𝙣𝙩𝙚𝙧[MAX_NODES], fils_lourd[MAX_NODES];

struct SegmentTree {
    int gauche, droite;
    long long retard, somme;
} arbre[MAX_NODES * 4];

void premier_parcours(int noeud, int ancetre, int prof) {
    profondeur[noeud] = prof;
    parent[noeud] = ancetre;
    taille[noeud] = 1;
    for (int voisin : adj[noeud]) {
        if (voisin == ancetre) continue;
        premier_parcours(voisin, noeud, prof + 1);
        taille[noeud] += taille[voisin];
        if (taille[fils_lourd[noeud]] < taille[voisin])
            fils_lourd[noeud] = voisin;
    }
}

void second_parcours(int noeud, int debut_chaine) {
    ordre_id[noeud] = ++compteur;
    valeur_seg[compteur] = valeur[noeud];
    tete[noeud] = debut_chaine;
    if (fils_lourd[noeud]) second_parcours(fils_lourd[noeud], debut_chaine);
    for (int voisin : adj[noeud]) {
        if (voisin == parent[noeud] || voisin == fils_lourd[noeud]) continue;
        second_parcours(voisin, voisin);
    }
}

void propager(int idx) {
    auto& courant = arbre[idx];
    auto& gauche = arbre[idx * 2];
    auto& droite = arbre[idx * 2 + 1];
    if (courant.retard) {
        gauche.retard += courant.retard;
        gauche.somme += courant.retard * (gauche.droite - gauche.gauche + 1);
        droite.retard += courant.retard;
        droite.somme += courant.retard * (droite.droite - droite.gauche + 1);
        courant.retard = 0;
    }
}

void construire(int idx, int l, int r) {
    arbre[idx] = {l, r, 0, valeur_seg[r]};
    if (l == r) return;
    int milieu = (l + r) / 2;
    construire(idx * 2, l, milieu);
    construire(idx * 2 + 1, milieu + 1, r);
    arbre[idx].somme = arbre[idx * 2].somme + arbre[idx * 2 + 1].somme;
}

void mettre_a_jour(int idx, int l, int r, int delta) {
    if (l <= arbre[idx].gauche && r >= arbre[idx].droite) {
        arbre[idx].retard += delta;
        arbre[idx].somme += delta * (arbre[idx].droite - arbre[idx].gauche + 1);
        return;
    }
    propager(idx);
    int milieu = (arbre[idx].gauche + arbre[idx].droite) / 2;
    if (l <= milieu) mettre_a_jour(idx * 2, l, r, delta);
    if (r > milieu) mettre_a_jour(idx * 2 + 1, l, r, delta);
    arbre[idx].somme = arbre[idx * 2].somme + arbre[idx * 2 + 1].somme;
}

long long interroger(int idx, int l, int r) {
    if (l <= arbre[idx].gauche && r >= arbre[idx].droite) 
        return arbre[idx].somme;
    propager(idx);
    int milieu = (arbre[idx].gauche + arbre[idx].droite) / 2;
    long long resultat = 0;
    if (l <= milieu) resultat += interroger(idx * 2, l, r);
    if (r > milieu) resultat += interroger(idx * 2 + 1, l, r);
    return resultat;
}

void modifier_chemin(int u, int v, int delta) {
    while (tete[u] != tete[v]) {
        if (profondeur[tete[u]] < profondeur[tete[v]]) swap(u, v);
        mettre_a_jour(1, ordre_id[tete[u]], ordre_id[u], delta);
        u = parent[tete[u]];
    }
    if (profondeur[u] < profondeur[v]) swap(u, v);
    mettre_a_jour(1, ordre_id[v], ordre_id[u], delta);
}

long long requete_chemin(int u, int v) {
    long long total = 0;
    while (tete[u] != tete[v]) {
        if (profondeur[tete[u]] < profondeur[tete[v]]) swap(u, v);
        total += interroger(1, ordre_id[tete[u]], ordre_id[u]);
        u = parent[tete[u]];
    }
    if (profondeur[u] < profondeur[v]) swap(u, v);
    total += interroger(1, ordre_id[v], ordre_id[u]);
    return total;
}

void modifier_sous_arbre(int noeud, int delta) {
    mettre_a_jour(1, ordre_id[noeud], ordre_id[noeud] + taille[noeud] - 1, delta);
}

long long requete_sous_arbre(int noeud) {
    return interroger(1, ordre_id[noeud], ordre_id[noeud] + taille[noeud] - 1);
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &valeur[i]);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    premier_parcours(1, 0, 1);
    second_parcours(1, 1);
    construire(1, 1, n);

    int requetes;
    scanf("%d", &requetes);
    while (requetes--) {
        int type, x;
        scanf("%d%d", &type, &x);
        if (type == 1) {
            int y, k;
            scanf("%d%d", &y, &k);
            modifier_chemin(x, y, k);
        } else if (type == 2) {
            int k;
            scanf("%d", &k);
            modifier_sous_arbre(x, k);
        } else if (type == 3) {
            int y;
            scanf("%d", &y);
            printf("%lld\n", requete_chemin(x, y));
        } else {
            printf("%lld\n", requete_sous_arbre(x));
        }
    }
    return 0;
}

Applicatoin concrète : Gestionnaire de paquets

Problème : Gérer l'installation/désinstallation de paquets logiciels dans une hiérarchie.

• Installer x : tous les nœuds du chemin racine vers x passent à l'état installé
• Désinstaller x : tout le sous-arbre enraciné en x passe à l'état désinstallé

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int LIMITE = 100010;

vector<int> enfants[LIMITE];
int compteur_global, profondeur[LIMITE], taille_arbre[LIMITE];
int segment_id[LIMITE], tete_chaine[LIMITE], pere[LIMITE], fils_preferentiel[LIMITE];

struct NoeudArbre {
    int gauche, droite;
    int marqueur, somme;
} arbre[LIMITE * 4];

void construire_arbre(int idx, int debut, int fin) {
    arbre[idx] = {debut, fin, -1, 0};
    if (debut == fin) return;
    int milieu = (debut + fin) / 2;
    construire_arbre(idx * 2, debut, milieu);
    construire_arbre(idx * 2 + 1, milieu + 1, fin);
}

void repousser_marque(int idx) {
    if (arbre[idx].marqueur != -1) {
        for (int enfant : {idx * 2, idx * 2 + 1}) {
            arbre[enfant].marqueur = arbre[idx].marqueur;
            arbre[enfant].somme = arbre[idx].marqueur * 
                (arbre[enfant].droite - arbre[enfant].gauche + 1);
        }
        arbre[idx].marqueur = -1;
    }
}

void mettre_a_jour_segment(int idx, int l, int r, int valeur) {
    if (l <= arbre[idx].gauche && r >= arbre[idx].droite) {
        arbre[idx].marqueur = valeur;
        arbre[idx].somme = valeur * (arbre[idx].droite - arbre[idx].gauche + 1);
        return;
    }
    repousser_marque(idx);
    int milieu = (arbre[idx].gauche + arbre[idx].droite) / 2;
    if (l <= milieu) mettre_a_jour_segment(idx * 2, l, r, valeur);
    if (r > milieu) mettre_a_jour_segment(idx * 2 + 1, l, r, valeur);
    arbre[idx].somme = arbre[idx * 2].somme + arbre[idx * 2 + 1].somme;
}

int lire_somme_globale() {
    return arbre[1].somme;
}

void parcours_initial(int noeud, int prof) {
    profondeur[noeud] = prof;
    taille_arbre[noeud] = 1;
    for (int fils : enfants[noeud]) {
        parcours_initial(fils, prof + 1);
        taille_arbre[noeud] += taille_arbre[fils];
        if (taille_arbre[fils_preferentiel[noeud]] < taille_arbre[fils])
            fils_preferentiel[noeud] = fils;
    }
}

void parcours_final(int noeud, int chaine_courante) {
    segment_id[noeud] = ++compteur_global;
    tete_chaine[noeud] = chaine_courante;
    if (fils_preferentiel[noeud]) 
        parcours_final(fils_preferentiel[noeud], chaine_courante);
    for (int fils : enfants[noeud]) {
        if (fils == fils_preferentiel[noeud]) continue;
        parcours_final(fils, fils);
    }
}

void appliquer_chemin(int source, int cible, int valeur) {
    while (tete_chaine[source] != tete_chaine[cible]) {
        if (profondeur[tete_chaine[source]] < profondeur[tete_chaine[cible]])
            swap(source, cible);
        mettre_a_jour_segment(1, segment_id[tete_chaine[source]], 
                            segment_id[source], valeur);
        source = pere[tete_chaine[source]];
    }
    if (profondeur[source] < profondeur[cible]) swap(source, cible);
    mettre_a_jour_segment(1, segment_id[cible], segment_id[source], valeur);
}

void appliquer_sous_arbre(int racine, int valeur) {
    mettre_a_jour_segment(1, segment_id[racine], 
                        segment_id[racine] + taille_arbre[racine] - 1, valeur);
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) {
        int parent_actuel;
        scanf("%d", &parent_actuel);
        parent_actuel++;
        enfants[parent_actuel].push_back(i);
        pere[i] = parent_actuel;
    }
    parcours_initial(1, 1);
    parcours_final(1, 1);
    construire_arbre(1, 1, n);

    int requetes;
    scanf("%d", &requetes);
    char operation[20];
    int cible;
    while (requetes--) {
        scanf("%s%d", operation, &cible);
        cible++;
        int ancienne_somme = lire_somme_globale();
        if (!strcmp(operation, "install")) {
            appliquer_chemin(1, cible, 1);
            printf("%d\n", lire_somme_globale() - ancienne_somme);
        } else {
            appliquer_sous_arbre(cible, 0);
            printf("%d\n", ancienne_somme - lire_somme_globale());
        }
    }
    return 0;
}