La gestion dynamique de points sur un maillage et le calcul du nombre d'éléments actifs à l'intérieur d'une zone rectangulaire relèvent de problèmes classiques en algorithmique. Lorsque les mises à jour ponctuelles et les requêtes d'intervalle sont fréquentes, la structure de données optimale est l'arbre de Fenwick bidimensionnel (Binary Indexed Tree 2D).

Extension du BIT à deux dimensions

Un arbre de Fenwick standard maintient un tableau unidimensionnel et permet de calculer des sommes préfixes en O(log N). Pour une matrice de taille N × M, on généralise le principe en considérant que chaque nœud bit[i][j] stocke la somme d'un sous-rectangle défini par les indices (i - lowbit(i) + 1, j - lowbit(j) + 1) et (i, j). La fonction utilitaire lowbit(v) = v & (-v) extrait le bit de poids faible non nul, permettant une navigation efficace dans la structure hiérarchique.

Mise à jour et requêtes préfixes

La modification d'une cellule (x, y) d'une valeur delta nécessite de propager cet incrément à tous les nœuds parents dans les deux dimensions. Le parcours se fait en augmentant les indices par ajout de leur lowbit.

void propagerValeur(int r, int c, int delta) {
    int i = r;
    while (i <= LIMITE) {
        int j = c;
        while (j <= LIMITE) {
            bit2D[i][j] += delta;
            j += j & -j;
        }
        i += i & -i;
    }
}

La fonction de requête interrogerPrefixe(r, c) retourne l'accumulation des valeurs dans le rectangle [1, r] × [1, c]. Elle opère en parcourent les indices vers l'origine en soustrayant systématiquement le lowbit.

long long interrogerPrefixe(int r, int c) {
    if (r < 1 || c < 1) return 0;
    long long res = 0;
    int i = r;
    while (i > 0) {
        int j = c;
        while (j > 0) {
            res += bit2D[i][j];
            j -= j & -j;
        }
        i -= i & -i;
    }
    return res;
}

Calcul de la somme sur un rectangle arbitraire

Un rectangle défini par deux sommets opposés (x1, y1) et (x2, y2) peut avoir ses coordonnées dans n'importe quel ordre. Il est indispensable de normaliser les bornes avant toute opération :

• x_min = min(x1, x2), x_max = max(x1, x2)
• y_min = min(y1, y2), y_max = max(y1, y2)

Le nombre total d'éléments actifs dans cette zone s'obtient directement via le principe d'inclusion-exclusion :

Somme = S(x_max, y_max) - S(x_min-1, y_max) - S(x_max, y_min-1) + S(x_min-1, y_min-1)

où S(r, c) désigne la fonction interrogerPrefixe. Cette formule élimine la nécessité de gérer des cas conditionnels complexes dans la logique principale.

Implémentation complète pour le problème des étoiles

Le scénario impose trois commandes : B pour allumer une étoile à des coordonnées précises, D pour l'éteindre, et Q pour interroger le nombre d'étoiles actives dans une zone rectangulaire. Un tableau d'état séparé est utilisé pour garantir l'idiempotence des commandes B et D (éviter de compter deux fois ou de supprimer une étoile déjà éteinte). Les coordonnées d'entrée étant généralement à base 0, elles sont décalées de +1 pour s'aligner sur l'indexage 1-based requis par le BIT.

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

const int DIM = 1005;
int etatEtoile[DIM][DIM]; // 0 : inactif, 1 : actif
int bit2D[DIM][DIM];      // Arbre de Fenwick bidimensionnel
const int LIMITE = 1001;

void propagerValeur(int r, int c, int delta) {
    int i = r;
    while (i <= LIMITE) {
        int j = c;
        while (j <= LIMITE) {
            bit2D[i][j] += delta;
            j += j & -j;
        }
        i += i & -i;
    }
}

long long interrogerPrefixe(int r, int c) {
    if (r < 1 || c < 1) return 0;
    long long res = 0;
    int i = r;
    while (i > 0) {
        int j = c;
        while (j > 0) {
            res += bit2D[i][j];
            j -= j & -j;
        }
        i -= i & -i;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int nbRequetes;
    if (!(cin >> nbRequetes)) return 0;

    while (nbRequetes--) {
        char operation;
        cin >> operation;
        if (operation == 'B') {
            int x, y;
            cin >> x >> y;
            x++; y++;
            if (!etatEtoile[x][y]) {
                etatEtoile[x][y] = 1;
                propagerValeur(x, y, 1);
            }
        } else if (operation == 'D') {
            int x, y;
            cin >> x >> y;
            x++; y++;
            if (etatEtoile[x][y]) {
                etatEtoile[x][y] = 0;
                propagerValeur(x, y, -1);
            }
        } else if (operation == 'Q') {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            x1++; y1++; x2++; y2++;

            int xmin = min(x1, x2);
            int xmax = max(x1, x2);
            int ymin = min(y1, y2);
            int ymax = max(y1, y2);

            long long resultat = interrogerPrefixe(xmax, ymax)
                               - interrogerPrefixe(xmin - 1, ymax)
                               - interrogerPrefixe(xmax, ymin - 1)
                               + interrogerPrefixe(xmin - 1, ymin - 1);
            cout << resultat << '\n';
        }
    }
    return 0;
}