1 Mise en place

L’objectif de ce TD est d’implémenter une nouvelle structure de données, les arbres de Fenwick, et de voir comment ils peuvent être utilisés pour calculer rapidement le nombre d’inversions dans un tableau.

2 Arbres de Fenwick

Dans cet exercice, on va construire une structure de données, appelée arbre de Fenwick, qui représente un tableau d’entiers avec des indices dans [L, H[ et qui permet d’exécuter les deux opération suivantes en temps O(log(H−L)) :

void inc(int i)

ajoute 1 à l’élément d’indice i du tableau représenté par this ; ne fait rien si i n’est pas dans [L, H[.

int cumulative(i)

renvoie la somme de tous les éléments du tableau représenté par this avec des indices dans ] − ∞, i[ ∩ [L, H[.

On peut penser à deux implémentations naïves :

• La première incrémente la case a[i] d’un tableau int[] a à chaque appel de inc(i) (temps constant) ; cumulative(i) renvoie la somme des a[j] pour 0 ≤ j < i (temps linéaire en H − L).
• La seconde stocke directement les valeurs de tous les cumulative(i), de sorte que cumulative(i) est calculé en temps constant mais c’est inc qui s’exécute en temps linéaire.

class Fenwick {
    private final Fenwick left;
    private final Fenwick right;
    private final int lo;
    private final int hi;
    private int acc;

}

Un arbre de Fenwick sur l’intervalle [L, H[ est défini comme suit. C’est un arbre binaire équilibré où chaque nœud a 0 ou 2 sous-arbres. Chaque nœud représente un intervalle. La racine correspond à l’intervalle [L,H[. Puis, pour tout nœud correspondant à l’intervalle [lo,hi[:

• si hi-lo > 1, alors le nœud a 2 sous-arbres qui correspondent respectivement aux deux intervalles disjoints [lo, mid[ et [mid, hi[ pour mid = ⌊(lo+hi)/2⌋.
• si hi-lo = 1, alors le nœud est une feuille et correspond à l’élément d’indice lo du tableau.

Chaque nœud d’un arbre de Fenwick stocke une valeur (représentée par le champ acc). Celle-ci est égale à la somme des valeurs des cases du tableau dont les indices sont dans [lo,hi[. En particulier, les feuilles contiennent juste la valeur de la case du tableau correspondante.

Le schéma ci-dessous illustre un arbre de Fenwick sur l’intervalle [0, 19[ représentant le tableau [2,2,3,1,0,0,1,1,2,0,1,3,4,2,0,0,2,1,3].

Toutes les méthodes de cette partie seront implémentées dans la classe Fenwick du fichier TD6.java.

class Fenwick {
    ...
    Fenwick(int lo, int hi) {
        /* TODO */
    }
}

class Fenwick {
    ...
    Fenwick get(int i) {
        /* TODO */
    }
}

2.3 Méthode inc

On veut maintenant implémenter la méthode inc. Un appel inc(i) incrémente les accumulateurs de tous les nœuds de l’arbre associés à un intervalle contenant i. L’appel ne fait rien si i n’est pas dans [lo, hi[. On implémentera cette méthode avec des appels récursifs.

Le schéma ci-dessous illustre l’appel inc(12). Les flèches jaunes représentent les appels récursifs. Les nœuds jaunes ont reçu un appel inc(12), incrémenté leurs compteurs et transmis l’appel à leurs sous-arbres. Les nœuds beiges ont reçu un appel inc(12) mais n’ont rien fait.

class Fenwick {
    ...
    void inc(int i) {
        /* TODO */
    }
}

Compléter la méthode inc.

La complexité doit être bornée par la profondeur de l’arbre.

Tester le code en exécutant Test23.java puis déposer TD6.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

2.4 Méthode cumulative

La méthode cumulative(i) renvoie la somme des éléments aux indices strictement inférieurs à i du tableau représenté par l’arbre. On remarque que si le nœud courant a des sous-arbres, alors cumulative(i) est égal à left.cumulative(i) + right.cumulative(i). Mais selon la valeur de i un calcul sans récursion est parfois possible.

Le schéma ci-dessous illustre l’appel cumulative(13). Il renvoie 21, la somme des nœuds jaunes (12+1+3+5), qui est aussi la somme des feuilles numérotées de 0 à 12. Les flèches jaunes représentent les appels récursifs. Les nœuds jaunes et beiges n’ont pas eu besoin de récursion pour renvoyer le résultat.

class Fenwick {
    ...
    int cumulative(int i) {
        /* TODO */
    }
}

Compléter la méthode cumulative.

La complexité doit être bornée par la profondeur de l’arbre.

Tester le code en exécutant Test24.java puis déposer TD6.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

3 Inversions dans un tableau.

On va maintenant utiliser les arbres de Fenwick pour dénombrer efficacement les inversions dans un tableau. Étant donné un tableau tab dont les indices sont compris dans [0,n[, on dit que la paire d’indices {i,j} forme une inversion si i<j et tab[i]>tab[j].

Par exemple dans le tableau [5,-2,10,3], il y a 3 inversions qui correspondent aux paires d’indices {0,1}, {0,3} et {2,3} (qui correspondent respectivement aux paires de valeurs {5,-2}, {5,3} et {10,3}).

Toutes les méthodes de cette partie seront implémentées dans la classe CountInversions du fichier TD6.java.

class CountInversions {
    ...
   static int countInversionsNaive(int[] a) {
        /* TODO */
    }
}

class CountInversions {
    ...
   static int countInversionsFen(int[] a) {
        /* TODO */
    }
}