Fonctionnalités

• Prétraitement en O(log n)
• Requête de maximum d'intervalle en O(1)
• Ne permet pas de modifier les valeurs du tableau

Pricnipe

Le principe fondamental des tables éparpilles est l'utilisation de la technique de "doublement" (ou exponentiation). On définit une structure de données f[i][j] qui représente le maximum dans l'intervalle partant de l'indice i et s'étendant sur 2^j éléments.

Cette approche fonctionne car n'importe quel intervalle de longueur len peut être couvert par au plus deux intervalles de la forme f[i][j].

Implémentation

Prétraitement

Le prétraitement suit une approche similaire à celle utilisée pour le LCA (Lowest Common Ancestor) avec doublement. La relation de récurrence est la suivante : f[i][j] = max(f[i][j-1], f[i + 2^(j-1)][j-1]). Cela revient à diviser l'inetrvalle en deux parties égales.

Voici le code pour le prétraitement :

const int MAX = 200010;
const int LOG = 18; // log2(MAX) arrondi

int n, m;
int donnees[MAX];
int st[MAX][LOG];
int logTable[MAX];

void pretraitement() {
    // Initialisation pour les intervalles de longueur 1
    for (int i = 1; i <= n; i++) {
        st[i][0] = donnees[i];
    }
    
    // Remplissage de la table ST
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = max(st[i][j-1], st[i + (1 << (j-1))][j-1]);
        }
    }
    
    // Précalcul des logarithmes pour optimiser les requêtes
    logTable[1] = 0;
    for (int i = 2; i < MAX; i++) {
        logTable[i] = logTable[i/2] + 1;
    }
}

Requête

La requête de maximum dans un intervalle [l, r] s'effectue en O(1) en utilisant la précalculée. La clé est de trouver les deux intervalles de puissance de deux qui couvrent complètement [l, r] sans le dépasser.

Voici la fonction de requête :

int requete(int gauche, int droite) {
    int longueur = droite - gauche + 1;
    int k = logTable[longueur];
    return max(st[gauche][k], st[droite - (1 << k) + 1][k]);
}

Exemple complet

Voici une implémentation complète des tables éparpilles :

/*
    Idée principale: doublement
    st[i][j] représente le maximum dans l'intervalle de taille 2^j commençant à i
    
    Prétraitement: O(n log n)
    Requête: O(1)
    
    Ne permet pas les modifications
    Idéal pour les requêtes fréquentes sur des tableaux statiques
*/

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int MAX_N = 200010;
const int LOG = 18;

int n, m;
int tableau[MAX_N];
int st[MAX_N][LOG];
int logTable[MAX_N];

void initialiser() {
    // Initialisation pour les intervalles de longueur 1
    for (int i = 1; i <= n; i++) {
        st[i][0] = tableau[i];
    }
    
    // Construction de la table ST
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = max(st[i][j-1], st[i + (1 << (j-1))][j-1]);
        }
    }
    
    // Précalcul des logarithmes
    logTable[1] = 0;
    for (int i = 2; i < MAX_N; i++) {
        logTable[i] = logTable[i/2] + 1;
    }
}

int interroger(int l, int r) {
    int longueur = r - l + 1;
    int k = logTable[longueur];
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> tableau[i];
    }
    
    initialiser();
    
    cin >> m;
    while (m--) {
        int gauche, droite;
        cin >> gauche >> droite;
        cout << interroger(gauche, droite) << "\n";
    }
    
    return 0;
}
</cmath></algorithm></iostream>

Comparaison avec les arbres de segment

Les arbres de segment offrent une alternative plus flexible avec une complexité de O(log n) pour les requêtes et les mises à jour, mais avec une constante plus élevée. Les tables éparpilles sont plus rapides pour les requêtes (O(1)) mais ne permettent pas les modifications, ce qui les rend idéales pour les tableaux statiques avec de nombreuses requêtes.

Voici une implémentation d'arbre de segment à titre de comparaison :

/*
    Implémentation d'arbre de segment pour le problème RMQ
    Complexité: O(log n) pour les requêtes et les mises à jour
*/

#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

const int MAX_N = 200010;

int n, m;
int valeurs[MAX_N];

struct Noeud {
    int debut, fin;
    int max_val;
} arbre[MAX_N * 4];

void remonter(int u) {
    arbre[u].max_val = max(arbre[u*2].max_val, arbre[u*2+1].max_val);
}

void construire(int u, int l, int r) {
    if (l == r) {
        arbre[u] = {l, l, valeurs[l]};
        return;
    }
    
    int mid = (l + r) / 2;
    construire(u*2, l, mid);
    construire(u*2+1, mid+1, r);
    
    arbre[u] = {l, r, max(arbre[u*2].max_val, arbre[u*2+1].max_val)};
}

int interroger(int u, int l, int r) {
    if (arbre[u].debut >= l && arbre[u].fin <= r) {
        return arbre[u].max_val;
    }
    
    int mid = (arbre[u].debut + arbre[u].fin) / 2;
    int max_val = INT_MIN;
    
    if (l <= mid) max_val = interroger(u*2, l, r);
    if (r > mid) max_val = max(max_val, interroger(u*2+1, l, r));
    
    return max_val;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> valeurs[i];
    }
    
    construire(1, 1, n);
    
    cin >> m;
    while (m--) {
        int l, r;
        cin >> l >> r;
        cout << interroger(1, l, r) << "\n";
    }
    
    return 0;
}
</climits></algorithm></iostream>