Prérequis

Avant de poursuivre, il est recommandé de maîtriser les concepts suivants :

• Le principe de la binary lifting (dilatation progressive).
• Les fondements de la programmation dynamique.
• L'implémentation de l'opérateur de décalage de bits (ex: 1 << k).

Introducsion à l'algorithme ST

L'algorithme ST (Sparse Table) est une solution efficace au problème du RMQ (Range Minimum/Maximum Query), qui consiste à déterminer la valeur minimale ou maximale au sein d'un sous-tableau donné.

Il s'appuie sur les paradigmes de la programmation dynamique et de la binary lifting. La phase de prétraitement a une complexité temporelle de O(n log n), tandis que chaque requête s'effectue en O(1). Cette structure est particulièrement adaptée aux scénarios où le nombre d'interrogations est élevé.

Détails d'implémentation

Explorons la construction d'une Sparse Table pour répondre aux requêtes de maximum d'intervalle.

Définissons un tableau 2D st[i][j] qui stocke la valeur maximale de l'intervalle commençant à l'indice i et de longueur 2^j.

Cas de base : Pour une longueur de 1 (j = 0), l'intervalle ne contient qu'un seul élément. Donc, st[i][0] = arr[i].

Récurrence : Un intervalle de longueur 2^j peut être divisé en deux sous-intervalles consécutifs de longueur 2^(j-1). Le maximum sur l'intervalle global est le maximum des deux maxima des sous-intervalles. La relation s'écrit : st[i][j] = max(st[i][j-1], st[i + (1 << (j-1))][j-1]). L'expression 1 << (j-1) calcule la valeur de 2^(j-1).

Lors du remplissage de la table, il est crucial d'itérer la variable de puissance j dans la boucle externe, et l'indice de départ i dans la boucle interne, pour garantir que les sous-problèmes plus petits soient résolus avant les plus grands.

La complexité de prétraitement est donc O(n log n).

// Prétraitement pour une table de maximums
void buildSparseTable(const vector<int>& data, vector<vector<int>>& table) {
    int n = data.size();
    // Niveaux de puissance (j)
    for (int power = 1; (1 << power) <= n; ++power) {
        // Indices de départ (i)
        for (int idx = 0; idx + (1 << power) - 1 < n; ++idx) {
            int step = 1 << (power - 1);
            table[idx][power] = max(table[idx][power - 1],
                                    table[idx + step][power - 1]);
        }
    }
}

Processus de requête

Pour interroger le maximum dans l'intervalle [L, R], nous pouvons couvrir cet intervalle avec deux blocs de longueur 2^k qui peuvent se chevaucher. Calculons k = log2(R - L + 1) (valeur entière inférieure).

Les deux intervalles à considérer sont : 1. Celui commençant à L et de longueur 2^k. 2. Celui commançant à R - (1 << k) + 1 et de longueur 2^k.

Puisque 2^k + 2^k = 2^(k+1) > (R - L + 1), l'union de ces deux intervalles couvre entièrement [L, R]. Le maximum sur [L, R] est donc : max(st[L][k], st[R - (1 << k) + 1][k]).

La requête s'effectue en temps constant.

// Requête de maximum sur [left, right]
int queryRMQ(const vector<vector<int>>& table, int left, int right) {
    int span = right - left + 1;
    int maxPower = log2(span);
    return max(table[left][maxPower],
               table[right - (1 << maxPower) + 1][maxPower]);
}

L'algorithme ST ne prend pas en charge les modifications efficaces des données sources. Cependant, pour les problèmes purement statiques (sans mise à jour), il représente une solution extrêmement performante.

Extensions de l'algorithme

L'idée centrale de la Sparse Table peut être appliquée à d'autres fonctions de combinaison qui sont idempotentes (c'est-à-dire où f(a, a) = a), car le chevauchement des intervalles n'affecte pas le résultat. Le maximum et le minimum sont idempotents.

Exemple : Requête GCD (Plus Grand Diviseru Commun) d'intervalle. La fonction GCD possède la propriété d'idempotence : gcd(a, a) = a. Ainsi, une Sparse Table peut répondre aux requêtes GCD. Il suffit de remplacer l'opérateur max par gcd dans les fonctions de construction et de requête.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> values(n);
    for (int i = 0; i < n; ++i) cin >> values[i];

    // Initialisation de la table
    vector<vector<int>> sparseTable(n, vector<int>(log2(n) + 1));
    for (int i = 0; i < n; ++i) sparseTable[i][0] = values[i];

    // Construction (remplacer max par gcd)
    for (int pwr = 1; (1 << pwr) <= n; ++pwr) {
        for (int idx = 0; idx + (1 << pwr) - 1 < n; ++idx) {
            sparseTable[idx][pwr] = gcd(sparseTable[idx][pwr - 1],
                                        sparseTable[idx + (1 << (pwr - 1))][pwr - 1]);
        }
    }

    // Traitement des requêtes
    while (m--) {
        int l, r;
        cin >> l >> r;
        --l; --r; // Passage en index 0
        int span = r - l + 1;
        int k = log2(span);
        int result = gcd(sparseTable[l][k],
                         sparseTable[r - (1 << k) + 1][k]);
        cout << result << "\n";
    }
    return 0;
}

Extension bidimensionnelle : Le concept peut être généralisé à des tableaux 2D pour répondre à des requêtes sur des sous-matrices, telles que le maximum dans une sous-matrice de dimensions fixes. La prétraitement consiste alors à construire des tables intermédiaires pour les lignes, puis pour les colonnes.