La structure d'arbre indexé binaire (Binary Indexed Tree, ou BIT) offre un compromis efficace entre mises à jour ponctuelles et requêtes sur des intervalles, avec une complexité logarithmique. Lorsqu'elle est appliquée à un tableau de différences, elle peut également gérer des modifications d'intervalle avec des requêtes ponctuelles.

Concept central

L'élément clé repose sur la fonction lowbit et le tableau auxiliaire tree. Chaque élément tree[i] représente la somme d'une sous-séquence du tableau original arr : de l'indice i - lowbit(i) + 1 jusqu'à i. Cela structure implicitement les données sous forme d'arbre.

Opérations de requête

Pour calculer la somme préfixe jusqu'à un indice x, on exploite les propriétés binaires. Par exemple, la somme de [1, 11] (en binaire 1011) se décompose en tree[1011] + tree[1010] + tree[1000]. Ce processus itératif enlève successivement le bit le moins significatif.

Voici une implémentation pour la somme préfixe :

int lowbit(int val) {
    return val & -val;
}

int prefix_sum(int index) {
    int total = 0;
    for (int idx = index; idx > 0; idx -= lowbit(idx)) {
        total += tree[idx];
    }
    return total;
}

Relations entre nœuds

Dans l'arbre implicite, ajouter successivement le lowbit courant à un indice permet d'identifier tous les ancêtres (nœuds parents), tandis que le soustraire révèle les descendants (nœuds enfants). C'est cette relation hiérarchique qui justifie la dénomination de l'arbre.

Opérations de mise à jour

Lorsqu'un élément arr[i] est modifié, tous les tree[j] qui l'incluent doivent être ajustés. L'algorithme parcourt les ancêtres en ajoutant le lowbit à chaque étape.

void update(int position, int delta) {
    for (int idx = position; idx <= size; idx += lowbit(idx)) {
        tree[idx] += delta;
    }
}

Initialisation du tableau tree

Plusieurs méthodes existent pour construire le BIT. Une approche directe utilise la relation :

// Méthode en O(n) basée sur les propriétés
for (int i = 1; i <= size; ++i) {
    prefix[i] = prefix[i - 1] + arr[i];
}
for (int i = 1; i <= size; ++i) {
    tree[i] = prefix[i] - prefix[i - lowbit(i)];
}

Utilisation avancée : modifications et requêtes d'intervalle

En combinant avec un tableau de différences, le BIT peut supporter des opérations d'intervalle avec une constante inférieure à celle d'un arbre de segments. Par exemple, pour maintenir la somme sur [l, r] avec des ajouts sur des intervalles, on utilise deux arbres indexés pour stocker des termes linéaires.

Extrait de code pour une implémentation complète :

#include <iostream>
#include <cstdio>
using namespace std;

typedef long long ll;
const int MAXN = 100005;

int arr[MAXN];
ll bit1[MAXN], bit2[MAXN];

int lowbit(int x) { return x & -x; }

void add_to_bit(ll tree[], int pos, ll val) {
    for (int i = pos; i <= MAXN; i += lowbit(i))
        tree[i] += val;
}

ll sum_from_bit(ll tree[], int pos) {
    ll res = 0;
    for (int i = pos; i; i -= lowbit(i))
        res += tree[i];
    return res;
}

ll range_sum(int idx) {
    return sum_from_bit(bit1, idx) * (idx + 1) - sum_from_bit(bit2, idx);
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &arr[i]);
        int diff = arr[i] - arr[i - 1];
        add_to_bit(bit1, i, diff);
        add_to_bit(bit2, i, (ll)diff * i);
    }
    while (m--) {
        char op[2];
        int l, r;
        scanf("%s %d %d", op, &l, &r);
        if (op[0] == 'C') {
            int d;
            scanf("%d", &d);
            add_to_bit(bit1, l, d);
            add_to_bit(bit2, l, l * d);
            add_to_bit(bit1, r + 1, -d);
            add_to_bit(bit2, r + 1, -(r + 1) * d);
        } else {
            printf("%lld\n", range_sum(r) - range_sum(l - 1));
        }
    }
    return 0;
}

Cette technique permet des opérations en O(log n) pour les mises à jour et requêtes d'intervalle, avec une empreinte mémoire réduite.