L'avantage principal d'une structure persistante réside dans sa capacité à gérer plusieurs versions de données à faible coût de stockage et de temps.

Arbre de segment persistant : code commenté

Un arbre de segment persistant (ou arbre du président) permet de conserver un historique complet des modifications sans réallouer entièrement la structure à chaque mise à jour. La version classique ne prend en charge que les modifications ponctuelles.

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

using namespace std;

const int MAXN = 100010;
const int MAXLOG = 17;

int nbElements, nbRequetes;
int valeursOrig[MAXN], valeursCompressees[MAXN], nbValeursUniques, compteur;
int racinesVersion[MAXN];

struct Noeud {
    int gauche, droite;  // indices des enfants
    int effectif;        // nombre d'éléments dans l'intervalle
} arbre[MAXN * 4 + MAXN * MAXLOG];

int compresser(int valeur) {
    int debut = 1, fin = nbValeursUniques;
    while (debut < fin) {
        int milieu = (debut + fin) >> 1;
        if (valeur <= valeursCompressees[milieu])
            fin = milieu;
        else
            debut = milieu + 1;
    }
    return debut;
}

int construireVide(int g, int d) {
    int idx = ++compteur;
    if (g == d) return idx;
    
    int milieu = (g + d) >> 1;
    arbre[idx].gauche = construireVide(g, milieu);
    arbre[idx].droite = construireVide(milieu + 1, d);
    return idx;
}

int insererElement(int noeudPrecedent, int g, int d, int position) {
    int nouveauNoeud = ++compteur;
    arbre[nouveauNoeud] = arbre[noeudPrecedent];
    
    if (g == d) {
        arbre[nouveauNoeud].effectif++;
        return nouveauNoeud;
    }
    
    int milieu = (g + d) >> 1;
    if (position <= milieu)
        arbre[nouveauNoeud].gauche = insererElement(arbre[noeudPrecedent].gauche, g, milieu, position);
    else
        arbre[nouveauNoeud].droite = insererElement(arbre[noeudPrecedent].droite, milieu + 1, d, position);
    
    arbre[nouveauNoeud].effectif = arbre[arbre[nouveauNoeud].gauche].effectif + arbre[arbre[nouveauNoeud].droite].effectif;
    return nouveauNoeud;
}

int rechercherKeme(int noeudR, int noeudL, int g, int d, int k) {
    if (g == d) return g;
    
    int milieu = (g + d) >> 1;
    int effectifGauche = arbre[arbre[noeudR].gauche].effectif - arbre[arbre[noeudL].gauche].effectif;
    
    if (effectifGauche >= k)
        return rechercherKeme(arbre[noeudR].gauche, arbre[noeudL].gauche, g, milieu, k);
    else
        return rechercherKeme(arbre[noeudR].droite, arbre[noeudL].droite, milieu + 1, d, k - effectifGauche);
}

int main() {
    scanf("%d %d", &nbElements, &nbRequetes);
    
    for (int i = 1; i <= nbElements; i++) {
        scanf("%d", &valeursOrig[i]);
        valeursCompressees[++nbValeursUniques] = valeursOrig[i];
    }
    
    sort(valeursCompressees + 1, valeursCompressees + nbValeursUniques + 1);
    nbValeursUniques = unique(valeursCompressees + 1, valeursCompressees + nbValeursUniques + 1) - valeursCompressees - 1;
    
    racinesVersion[0] = construireVide(1, nbValeursUniques);
    
    for (int i = 1; i <= nbElements; i++) {
        racinesVersion[i] = insererElement(racinesVersion[i - 1], 1, nbValeursUniques, compresser(valeursOrig[i]));
    }
    
    while (nbRequetes--) {
        int debut, fin, rang;
        scanf("%d %d %d", &debut, &fin, &rang);
        printf("%d\n", valeursCompressees[rechercherKeme(racinesVersion[fin], racinesVersion[debut - 1], 1, nbValeursUniques, rang)]);
    }
    
    return 0;
}

Modèle généralisé

Ce modèle peut stocker n'importe quelle information agrégée (maximum, minimum, somme, etc.) tout en préservant l'historique complet des modifications.

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

using namespace std;

const int MAXN = 1000010;
const int MAXLOG = 20;

int nbElements, nbOperations;
int racines[MAXN], valeurs[MAXN], compteur;

struct Noeud {
    int gauche, droite;
    int valeurMax;
} arbre[MAXN * 4 + MAXN * MAXLOG];

void propagerMax(int idx) {
    arbre[idx].valeurMax = max(arbre[arbre[idx].gauche].valeurMax, arbre[arbre[idx].droite].valeurMax);
}

int construireArbre(int g, int d) {
    int idx = ++compteur;
    if (g == d) {
        arbre[idx].valeurMax = valeurs[g];
        return idx;
    }
    
    int milieu = (g + d) >> 1;
    arbre[idx].gauche = construireArbre(g, milieu);
    arbre[idx].droite = construireArbre(milieu + 1, d);
    propagerMax(idx);
    return idx;
}

int mettreAJour(int noeudAncien, int g, int d, int position, int nouvelleValeur) {
    int nouveauNoeud = ++compteur;
    arbre[nouveauNoeud] = arbre[noeudAncien];
    
    if (g == d) {
        arbre[nouveauNoeud].valeurMax = nouvelleValeur;
        return nouveauNoeud;
    }
    
    int milieu = (g + d) >> 1;
    if (position <= milieu)
        arbre[nouveauNoeud].gauche = mettreAJour(arbre[noeudAncien].gauche, g, milieu, position, nouvelleValeur);
    else
        arbre[nouveauNoeud].droite = mettreAJour(arbre[noeudAncien].droite, milieu + 1, d, position, nouvelleValeur);
    
    propagerMax(nouveauNoeud);
    return nouveauNoeud;
}

int interroger(int noeud, int g, int d, int position) {
    if (g == d) return arbre[noeud].valeurMax;
    
    int milieu = (g + d) >> 1;
    if (position <= milieu)
        return interroger(arbre[noeud].gauche, g, milieu, position);
    else
        return interroger(arbre[noeud].droite, milieu + 1, d, position);
}

int main() {
    scanf("%d %d", &nbElements, &nbOperations);
    
    for (int i = 1; i <= nbElements; i++) {
        scanf("%d", &valeurs[i]);
    }
    
    racines[0] = construireArbre(1, nbElements);
    
    int nbVersions = 0;
    while (nbOperations--) {
        int versionBase, typeOp, pos, val;
        scanf("%d %d", &versionBase, &typeOp);
        
        if (typeOp == 1) {
            scanf("%d %d", &pos, &val);
            racines[++nbVersions] = mettreAJour(racines[versionBase], 1, nbElements, pos, val);
        } else {
            scanf("%d", &pos);
            racines[++nbVersions] = racines[versionBase];
            printf("%d\n", interroger(racines[versionBase], 1, nbElements, pos));
        }
    }
    
    return 0;
}

Approche alternative pour la recherche du k-ème élément

Une méthode différente consiste à trier les éléments puis à construire progressivement des versions où chaque insertion ajoute un élément dans l'ordre croissant. La recherche s'effectue par dichotomie sur le numéro de version.

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

using namespace std;

const int MAXN = 100010;

int nbElements, nbRequetes;
int compteur, racines[MAXN];

struct Element {
    int valeur;
    int positionOriginale;
    bool operator<(const Element& autre) const {
        return valeur < autre.valeur;
    }
} elements[MAXN];

struct NoeudArbre {
    int gauche, droite;
    int valeurStockee;
    int effectif;
} arbre[MAXN * 4 + MAXN * 20];

void propagerEffectif(int idx) {
    arbre[idx].effectif = arbre[arbre[idx].gauche].effectif + arbre[arbre[idx].droite].effectif;
}

int construireBase(int g, int d) {
    int idx = ++compteur;
    if (g == d) {
        arbre[idx].valeurStockee = -1e9;
        arbre[idx].effectif = 0;
        return idx;
    }
    
    int milieu = (g + d) >> 1;
    arbre[idx].gauche = construireBase(g, milieu);
    arbre[idx].droite = construireBase(milieu + 1, d);
    return idx;
}

int ajouterElement(int noeudAncien, int g, int d, int position, int valeur) {
    int nouveauNoeud = ++compteur;
    arbre[nouveauNoeud] = arbre[noeudAncien];
    
    if (g == d) {
        arbre[nouveauNoeud].valeurStockee = valeur;
        if (valeur > -1e9) arbre[nouveauNoeud].effectif = 1;
        return nouveauNoeud;
    }
    
    int milieu = (g + d) >> 1;
    if (position <= milieu)
        arbre[nouveauNoeud].gauche = ajouterElement(arbre[noeudAncien].gauche, g, milieu, position, valeur);
    else
        arbre[nouveauNoeud].droite = ajouterElement(arbre[noeudAncien].droite, milieu + 1, d, position, valeur);
    
    propagerEffectif(nouveauNoeud);
    return nouveauNoeud;
}

int compterIntervalle(int noeud, int g, int d, int debut, int fin) {
    if (debut > d || fin < g) return 0;
    if (debut <= g && d <= fin) return arbre[noeud].effectif;
    
    int milieu = (g + d) >> 1;
    return compterIntervalle(arbre[noeud].gauche, g, milieu, debut, fin) +
           compterIntervalle(arbre[noeud].droite, milieu + 1, d, debut, fin);
}

bool verifierCondition(int versionTest, int debut, int fin, int seuil) {
    return compterIntervalle(racines[versionTest], 1, nbElements, debut, fin) >= seuil;
}

int main() {
    scanf("%d %d", &nbElements, &nbRequetes);
    
    racines[0] = construireBase(1, nbElements);
    
    for (int i = 1; i <= nbElements; i++) {
        scanf("%d", &elements[i].valeur);
        elements[i].positionOriginale = i;
    }
    
    sort(elements + 1, elements + nbElements + 1);
    
    for (int i = 1; i <= nbElements; i++) {
        racines[i] = ajouterElement(racines[i - 1], 1, nbElements, elements[i].positionOriginale, elements[i].valeur);
    }
    
    while (nbRequetes--) {
        int debut, fin, rang;
        scanf("%d %d %d", &debut, &fin, &rang);
        
        int borneInf = 0, borneSup = nbElements, milieu;
        while (borneInf < borneSup) {
            milieu = (borneInf + borneSup) >> 1;
            if (verifierCondition(milieu, debut, fin, rang))
                borneSup = milieu;
            else
                borneInf = milieu + 1;
        }
        
        printf("%d\n", elements[borneInf].valeur);
    }
    
    return 0;
}