Introduction

L'arbre de Fenwick est une structure de données efficace pour gérer les sommes préfixes. Il offre des opérations rapides de mise à jour et de requête avec une complexité logarithmique.

Fonction lowbit

L'opération fondamentale lowbit(x) = x & -x isole le bit le plus bas à 1 dans la représantation binaire d'un nombre.

Principe de stockage

La structure utilise un tableau arbre où chaque élément arbre[i] stocke la somme des éléments de l'intervalle [i - lowbit(i) + 1, i]. Cette décomposition binaire permet des opérations efficaces.

Implémentation

Requête de somme préfixe

int sommePrefixe(int pos) {
    int total = 0;
    for (int idx = pos; idx > 0; idx -= lowbit(idx)) 
        total += arbre[idx];
    return total;
}

Mise à jour d'élément

void mettreAJour(int pos, int valeur) {
    for (int idx = pos; idx <= n; idx += lowbit(idx))
        arbre[idx] += valeur;
}

Initialisation

void initialiser() {
    for (int i = 1; i <= n; i++)
        mettreAJour(i, donnees[i]);
}

Applications pratiques

Problème P3374

Mises à jour ponctuelles et requêtes d'intervalle :

int main() {
    cin >> taille >> requetes;
    for (int i = 1; i <= taille; i++) {
        cin >> donnees[i];
        mettreAJour(i, donnees[i]);
    }
    while (requetes--) {
        int type, x, y;
        cin >> type >> x >> y;
        if (type == 1) mettreAJour(x, y);
        else cout << sommePrefixe(y) - sommePrefixe(x - 1) << "\n";
    }
}

Problème P3368

Mises à jour par intervalle avec tableau de différences :

int main() {
    cin >> taille >> requetes;
    for (int i = 1; i <= taille; i++) {
        cin >> donnees[i];
        mettreAJour(i, donnees[i] - donnees[i - 1]);
    }
    while (requetes--) {
        int op, x, y, k;
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> k;
            mettreAJour(x, k);
            mettreAJour(y + 1, -k);
        } else {
            cin >> x;
            cout << sommePrefixe(x) << "\n";
        }
    }
}

Requêtes et mises à jour par intervalle

Solution avec deux arbres de Fenwick :

int requeteComplete(int x) {
    return sommePrefixe(arbre1, x) * (x + 1) - sommePrefixe(arbre2, x);
}

Problème P1908 (Inversions)

Comptage d'inversions avec compression de valeurs :

int main() {
    cin >> taille;
    for (int i = 1; i <= taille; i++) {
        cin >> donnees[i];
        valeurs[i] = donnees[i];
    }
    sort(valeurs + 1, valeurs + taille + 1);
    int elementsUniques = unique(valeurs + 1, valeurs + taille + 1) - valeurs - 1;
    long long inversions = 0;
    for (int i = taille; i >= 1; i--) {
        int pos = lower_bound(valeurs + 1, valeurs + elementsUniques + 1, donnees[i]) - valeurs;
        inversions += sommePrefixe(pos - 1);
        mettreAJour(pos, 1);
    }
    cout << inversions << "\n";
}